স্পার্স টেবিল (Sparse Table) একটি ডেটা স্ট্রাকচার (data structure), যা রেঞ্জ কোয়েরি (range queries) এর ফলাফল দিতে ব্যবহৃত হয়। এটি অধিকাংশ রেঞ্জ কোয়েরির ফলাফল O(logN) কমপ্লেক্সিটিতে দেয়। ম্যাক্সিমাম (maximum) রেঞ্জ কোয়েরির জন্য এটি O(1)-এও ফলাফল ক্যালকুলেট করতে পারে।
এই টিউটোরিয়ালে, আমরা স্পার্স টেবিল ব্যবহার করে রেঞ্জ সম কোয়েরি (Range Sum Query) সমস্যা আলোচনা করব যেখানে আমাদের একটি অ্যারে দেওয়া আছে এবং আমাদের L এবং R রেঞ্জের সব উপাদানের যোগফল বের করতে হবে। উদাহরণস্বরূপ:
Input: arr[ ] = { 2, 4, 1, 5, 6, 3 } query(1, 3), query(0,2), query(1, 5). Output: 10 7 19 Input: arr[ ] = { 1, 2, 3, 4, 1, 4 } query(0, 2), query(2,4), query(3, 5). Output: 6 8 9
সমাধানের পদ্ধতি
প্রথমে আমাদের একটি স্পার্স টেবিল তৈরি করতে হবে সেটিতে উত্তর খুঁজে বের করার জন্য। স্পার্স টেবিল তৈরি করার জন্য, আমরা একটি ২-ডি অ্যারে ব্যবহার করি উত্তরগুলো সংরক্ষণ করার জন্য। স্পার্স টেবিলে, আমরা কোয়েরিগুলোকে ২-এর ঘাতে ভাঙি। স্পার্স টেবিল তৈরি হওয়ার পর, আমরা সেটিতে কোয়েরি সার্চ করি এবং একটি ভেরিয়েবলে মান যোগ করতে থাকি শর্তমত ( Left_index + 2^n - 1 <= Right_index ) যেখানে n হলো ২-ডি অ্যারে কলামের আকার।
উদাহরণ
উপরোক্ত পদ্ধতির জন্য C++ কোড
#include <bits/stdc++.h> using namespace std; // স্পার্স টেবিলের সারি (row) এর সর্বোচ্চ মান। const int m = 1e5; const int n = 16; long long SPARSE[m][n + 1]; // স্পার্স টেবিলের সাহায্যে কোয়েরি বের করা। long long query(int l, int r){ long long sum = 0; for (int i = n; i >= 0; i--) { if (l + (1 << i) - 1 <= r) { sum = sum + SPARSE[l][i]; l += 1 << i; } } return sum; } int main(){ int arr[] = { 1, 2, 3, 4, 1, 4 }; int z = sizeof(arr) / sizeof(arr[0]); // স্পার্স টেবিল তৈরি করুন। for (int i = 0; i < z; i++) SPARSE[i][0] = arr[i]; for (int i = 1; i <= n; i++) for (int j = 0; j <= z - (1 << j); j++) SPARSE[j][i] = SPARSE[j][i - 1] + SPARSE[j + (1 << (i - 1))][i - 1]; cout <<"Sum: " << query(0, 2) << endl; cout <<"Sum: " << query(2, 4) << endl; cout <<"Sum: " << query(3, 5) << endl; return 0; }
আউটপুট
Sum: 6 Sum: 8 Sum: 4
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি স্পার্স টেবিল তৈরি করার কথা আলোচনা করেছি যা রেঞ্জ কোয়েরির জন্য খুবই উপকারী। আমরা একটি সহজ পদ্ধতি আলোচনা করেছি স্পার্স টেবিল তৈরি করে এবং সেটি থেকে কোয়েরির ফলাফল বের করে। আমরা এই সমস্যার জন্য C++ প্রোগ্রামও আলোচনা করেছি যা আমরা C, Java, Python ইত্যাদি প্রোগ্রামিং ভাষায়ও করতে পারি। আশা করি আপনি এই টিউটোরিয়ালটিকে উপকারী পাবেন।
