Sparse Table


Sparse Table RMQ (range minimum/maximum query) টাইপ প্রবলেম সল্ভ করতে কাজে লাগে। একটি Array ‘A’ তে কিছু নাম্বার দেয়া আছে। এখন বলা হল কুয়েরি i to j রেঞ্জ দেয়া হবে, বলতে হবে এই রেঞ্জে এর মধ্যে মিনিমাম নাম্বার কত। এখন Brute force way তে করলে worst case complexity যাবে O(Q*N)। কিন্তু Sparse Table দিয়ে O(N log N) এ pre calculation করে O(1) এ প্রতি কুয়েরির answer দেয়া যায়।

Sparse Table:

Sparse Table এ Array প্রতিপজিশন থেকে তার 2 এর power এর length পর্যন্ত result সেভ করে রাখা হয়।এর ফলে, “যেকোন নাম্বারকে 2 এর power এর যোগফল হিসেবে লিখা যায়।” এই property use করে sparse table থেকে সহজে result calculation করা যায়।

Array A[]={10, 1, 3, 20, 25, -5, 6, -10, 11, 8} এর minimum range query জন্য sparse table ST হবে এমন,Capture

  • এখন টেবিলের 0th row এ থাকবে Array এর প্রতি পজিশন থেকে 1 length এর result. তারমানে 0th row তে থাকবে initial Array।
  • টেবিলের 1st row এ থাকবে, Array এর প্রতি পজিশন থেকে 2¹=2 length এর minimum result.
    • ST[1][0] এ থাকবে ০ to 1 length এর minimum result.
    • ST[1][1] এ থাকবে 1 to 2 length এর minimum result.
    • ST[1][2] এ থাকবে 2 to 3 length এর minimum result.
    • ST[1][3] এ থাকবে 3 to 4 length এর minimum result.
    • ST[1][4] এ থাকবে 4 to 5 length এর minimum result.
    • ST[1][5] এ থাকবে 5 to 6 length এর minimum result.
    • ST[1][6] এ থাকবে 6 to 7 length এর minimum result.
    • ST[1][7] এ থাকবে 7 to 8 length এর minimum result.
    • ST[1][8] এ থাকবে 8 to 9 length এর minimum result.
  • টেবিলের 2nd row এ থাকবে, Array এর প্রতি পজিশন থেকে 2²=4 length এর minimum result.
    • ST[2][0] এ থাকবে ০ to 3 length এর minimum result.
    • ST[2][1] এ থাকবে 1 to 4 length এর minimum result.
    • ST[2][2] এ থাকবে 2 to 5 length এর minimum result.
    • ST[2][3] এ থাকবে 3 to 6 length এর minimum result.
    • ST[2][4] এ থাকবে 4 to 7 length এর minimum result.
    • ST[2][5] এ থাকবে 5 to 8 length এর minimum result.
    • ST[2][6] এ থাকবে 6 to 9 length এর minimum result.
  • টেবিলের 3rd row এ থাকবে, Array এর প্রতি পজিশন থেকে 2³=8 length এর minimum result.
    • ST[3][0] এ থাকবে ০ to 7 length এর minimum result.
    • ST[3][1] এ থাকবে 1 to 8 length এর minimum result.
    • ST[3][2] এ থাকবে 2 to 9 length এর minimum result.

 

Sparse Table Compute:

ধরা যাক, Sparse Table ST[row][col] এর row নির্দেশ করে 2 এর পাওয়ার এবং col নির্দেশ করে Array এর position. এখন 2length এর জন্য প্রতি পজিশন থেকে result ক্যালকুলেট করব এবং Sparse Table এ calculate করা আছে 2K-1 length পর্যন্ত result. তাহলে sparse table ST[K][i] এর result হবে, ST[K-1][i]ST[K-1][i+(2K-1 )] এর মিনিমাম। কারন 2কে লেখা যায় 2K = 2K-1 +2K-1

Code: compute sparse table


Sparse Table pre calculation এর complexity হল O(N log2 N). এখানে k লুপ iterate হচ্ছে log2N টাইম এবং i লুপ iterate হচ্ছে N টাইম।
Table এর জন্য memory লাগছে, Nlog2N সংখ্যক।

Query:

Code: Query


Query জন্য i to j রেঞ্জ এর length কে log2 ফেক্টর করে দুইভাগে result calculation করা হচ্ছে।  Query complexity হচ্ছে O(1).

All together:

Code: Sparse Table

Reference:

Practice problem:

Advertisements

About Tanvir Hasan Anick

I can read and write code, :)
This entry was posted in Contest, Data structure, Programming and tagged . Bookmark the permalink.

One Response to Sparse Table

  1. Rajon Bardhan says:

    Another nice tutorial . Helps me a lot . Thanks .

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s