স্পার্স টেবিল (Sparse Table)
ধরুন আপনার কাছে অনেক বড় একটা সংখ্যার অ্যারে আছে, আর আপনাকে বারবার বিভিন্ন রেঞ্জের প্রশ্ন করা হচ্ছে: "৩ নম্বর থেকে ১১ নম্বর ইনডেক্সের মধ্যে সবচেয়ে ছোট সংখ্যা কোনটা?" সাধারণ লুপ চালিয়ে প্রতিটার উত্তর বের করতে O(n) সময় লাগবে। সেগমেন্ট ট্রি (Segment tree) ব্যবহার করলে প্রতিটার উত্তর বের করতে O(log n) সময় লাগবে। কিন্তু স্পার্স টেবিল (Sparse table) এমন জাদুকরী একটা জিনিস, যেটা প্রতিটা প্রশ্নের উত্তর জাস্ট O(1) বা চোখের পলকে দিয়ে দিতে পারে — তবে হ্যাঁ, এর জন্য শুরুতে একবার O(n log n) সময় খরচ করে টেবিলটা সাজিয়ে নিতে হয়।
এর একটা বড় শর্ত আছে: স্পার্স টেবিল শুধুমাত্র আইডেমপোটেন্ট অপারেশনের (idempotent operations) জন্য কাজ করে — অর্থাৎ এমন সব কাজ, যেখানে কোনো সংখ্যা দুবার হিসাব (double-count) হলেও ফাইনাল রেজাল্টে কোনো ভেজাল হয় না। যেমন, কোনো রেঞ্জের সবচেয়ে ছোট (min) বা সবচেয়ে বড় (max) সংখ্যা বের করা: min(min(a,b), min(b,c)) = min(a,b,c)। কিন্তু যোগফলের (sum) ক্ষেত্রে এটা কাজ করবে না — কারণ একই সংখ্যা দুবার যোগ করলে মোট যোগফল বদলে গিয়ে ভুল উত্তর আসবে।
আসল বুদ্ধি — ২-এর পাওয়ারের লাভ (Power-of-2 intervals)
স্পার্স টেবিল আগে থেকেই এমন সব রেঞ্জের উত্তর হিসাব করে রাখে, যাদের সাইজ বা দৈর্ঘ্য হলো ২-এর পাওয়ার: যেমন ১, ২, ৪, ৮, ১৬... ইত্যাদি। এখন কেউ যদি যেকোনো একটা রেঞ্জের [L, R] উত্তর জানতে চায়, আপনি সবসময় ওই রেঞ্জটাকে পুরোপুরি কাভার করার মতো ২-এর পাওয়ার সাইজের দুটো রেঞ্জ দিয়ে ঢেকে দিতে পারবেন। যেহেতু আমরা ছোট/বড় (min/max) খুঁজছি, তাই রেঞ্জ দুটোর মাঝখানে ওভারল্যাপ (overlap) বা কমন কিছু পড়ে গেলেও আমাদের উত্তরের কোনো ক্ষতি হবে না।
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
কীভাবে টেবিলটা বানানো হয়?
ধরি table[j][i] মানে হলো i নম্বর ইনডেক্স থেকে শুরু হওয়া 2^j দৈর্ঘ্যের রেঞ্জের সবচেয়ে ছোট সংখ্যা।
- বেস কেস বা শুরু (j=0):
table[0][i] = arr[i]— অর্থাৎ ১ দৈর্ঘ্যের রেঞ্জের মান অ্যারের ওই সংখ্যার সমান। - পরের ধাপগুলোর সূত্র:
table[j][i] = min(table[j-1][i], table[j-1][i + 2^(j-1)])
প্রতিটা লেভেলে রেঞ্জের দৈর্ঘ্য দ্বিগুণ হতে থাকে। এভাবে log₂(n) বা আড়াই-তিন লেভেল পর্যন্ত হিসাব করতে হয়, আর প্রতি লেভেলে O(n) কাজ থাকে — তাই টোটাল সময় লাগে O(n log n)।
চোখের পলকে বা O(1) স্পিডে উত্তর দেওয়া
একটা নির্দিষ্ট রেঞ্জ [L, R]-এর উত্তর বের করতে হলে:
- প্রথমে ওই রেঞ্জের সাইজের চেয়ে ছোট বা সমান ২-এর সবচেয়ে বড় পাওয়ারটা বের করতে হয়: k = floor(log₂(R - L + 1))
- তারপর জাস্ট এই দুটোর মধ্যে ছোটটা রিটার্ন করতে হয়:
min(table[k][L], table[k][R - 2^k + 1])
এই দুটো ওভারল্যাপিং (overlapping) রেঞ্জ মিলে পুরো [L, R] রেঞ্জটাকে সুন্দরভাবে কাভার করে ফেলে। আর যেহেতু min ফাংশনে ওভারল্যাপ হলেও ক্ষতি নেই, তাই মাত্র দুইবার টেবিলে লুকআপ (lookup) করেই O(1) স্পিডে উত্তর পাওয়া যায়।
কখন স্পার্স টেবিল ব্যবহার করবেন?
- যখন অ্যারেটা স্ট্যাটিক বা ফিক্সড থাকে, অর্থাৎ বানালে আর কখনো চেঞ্জ হয় না।
- যখন প্রচুর পরিমাণে রেঞ্জ মিনিমাম বা ম্যাক্সিমাম কোয়ারির (RMQ) উত্তর দিতে হয়।
- যখন ডেটা আপডেটের চেয়ে প্রতিটা উত্তরের স্পিড O(1) হওয়াটা বেশি জরুরি।
যদি অ্যারের ডেটা বারবার চেঞ্জ বা আপডেট হয়, তবে স্পার্স টেবিলের বদলে সেগমেন্ট ট্রি (Segment tree) বা ফেনউইক ট্রি (Fenwick tree) ব্যবহার করা ভালো — ওরা O(log n) স্পিডে আপডেট সাপোর্ট করে, যদেবেন উত্তর খোঁজার স্পিডও তখন O(log n) হয়ে যায়।
Complexity
ছোট কুইজ
পড়া চালিয়ে যান