स्पार्स टेबल एक डेटा संरचना है, जिसका उपयोग रेंज क्वेरी के परिणाम देने के लिए किया जाता है। यह अधिकांश रेंज क्वेरी के परिणाम को O(logN) जटिलता में प्रदान करता है। अधिकतम रेंज क्वेरी के लिए, यह O(1) में भी परिणाम की गणना कर सकता है।
यह ट्यूटोरियल स्पार्स टेबल का उपयोग करके रेंज सम क्वेरी की समस्या पर चर्चा करेगा जहां हमें एक एरे दिया गया है। हमें रेंज L और R में सभी तत्वों का योग खोजने की आवश्यकता है, उदाहरण के लिए।
इनपुट: arr[] = {2, 4, 1, 5, 6, 3} query(1, 3), query(0,2), query(1, 5).
आउटपुट: 10 7 19
इनपुट: arr[] = {1, 2, 3, 4, 1, 4} query(0, 2), query(2,4), query(3, 5).
आउटपुट: 6 8 9
समाधान खोजने का दृष्टिकोण
सबसे पहले हमें स्पार्स टेबल बनाने की आवश्यकता है ताकि हम स्पार्स टेबल में उत्तर खोज सकें। स्पार्स टेबल बनाने में, हम उत्तरों को स्टोर करने के लिए 2-D एरे का उपयोग करते हैं। स्पार्स टेबल में, हम क्वेरी को 2 की घात में तोड़ते हैं। स्पार्स टेबल बनाने के बाद, हम उस टेबल में क्वेरी खोजते हैं और एक वेरिएबल में मान जोड़ते रहते हैं (Left_index + 2^n - 1 <= Right_index) की शर्त पर जहां n 2-D एरे के कॉलम का आकार है।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h>
using namespace std;
// स्पार्स टेबल की पंक्ति का अधिकतम मान।
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 << "योग: " << query(0, 2) << endl;
cout << "योग: " << query(2, 4) << endl;
cout << "योग: " << query(3, 5) << endl;
return 0;
}
आउटपुट
योग: 6 योग: 8 योग: 4
निष्कर्ष
इस ट्यूटोरियल में, हमने स्पार्स टेबल बनाने पर चर्चा की जो रेंज क्वेरी के लिए बहुत उपयोगी है। हमने स्पार्स टेबल निर्माण और उस टेबल से क्वेरी परिणाम प्राप्त करके इस समस्या को हल करने के एक सरल दृष्टिकोण पर चर्चा की। हमने इस समस्या के लिए C++ प्रोग्राम पर भी चर्चा की जिसे हम C, Java, Python आदि प्रोग्रामिंग भाषाओं के साथ कर सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।
