Sparsh Table হল একটি ডেটা স্ট্রাকচার, যা রেঞ্জ কোয়েরির ফলাফল দিতে ব্যবহৃত হয়। এটি O(logN) জটিলতায় বেশিরভাগ পরিসরের প্রশ্নের ফলাফল প্রদান করে। সর্বাধিক পরিসরের প্রশ্নের জন্য, এটি O(1) তেও ফলাফল গণনা করতে পারে।
এই টিউটোরিয়ালটি একটি স্পার্স টেবিল ব্যবহার করে একটি রেঞ্জ যোগ কোয়েরির সমস্যা নিয়ে আলোচনা করবে যেখানে আমাদের একটি অ্যারে দেওয়া হয়েছে। আমাদের 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 সমাধান খোঁজার পদ্ধতি
একটি স্পার্স টেবিলে উত্তর অনুসন্ধান করার জন্য প্রথমে আমাদের একটি স্পার্স টেবিল তৈরি করতে হবে। একটি স্পার্স টেবিল তৈরি করার সময়, আমরা উত্তরগুলি সংরক্ষণ করার জন্য একটি 2-ডি অ্যারে ব্যবহার করি। স্পার্স টেবিলে, আমরা 2 এর শক্তিতে প্রশ্নগুলিকে বিরতি করি। একটি স্পার্স টেবিল তৈরি করার পরে, আমরা সেই টেবিলে প্রশ্নগুলি অনুসন্ধান করি এবং ( Left_index + 2^n - 1 <=Right_index) শর্তে একটি ভেরিয়েবলে মান যোগ করতে থাকি ) যেখানে n হল একটি 2-D অ্যারের কলামের আকার।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include <bits/stdc++.h>
using namespace std;
// Maximum value of row of sparse table.
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];
// query to be found with the help of a sparse table.
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]);
// Building sparse table.
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++ প্রোগ্রাম নিয়েও আলোচনা করেছি যা আমরা সি, জাভা, পাইথন ইত্যাদি প্রোগ্রামিং ভাষার সাথে করতে পারি। আমরা আশা করি এই টিউটোরিয়ালটি আপনার কাজে লাগবে।
