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