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 হবে এমন,

• এখন টেবিলের 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. এখন 2^K length এর জন্য প্রতি পজিশন থেকে result ক্যালকুলেট করব এবং Sparse Table এ calculate করা আছে 2^K-1 length পর্যন্ত result. তাহলে sparse table ST[K][i] এর result হবে, ST[K-1][i] ও ST[K-1][i+(2^K-1 )] এর মিনিমাম। কারন 2^K কে লেখা যায় 2^K = 2^K-1 +2^K-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:

• Top Coder.

Practice problem:

• Chef and Array