स्पर्श तालिका एक डेटा संरचना है, जिसका उपयोग श्रेणी प्रश्नों के परिणाम देने के लिए किया जाता है। यह 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-डी सरणी के कॉलम का आकार है।
उदाहरण
उपरोक्त दृष्टिकोण के लिए 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++ प्रोग्राम पर भी चर्चा की जिसे हम प्रोग्रामिंग भाषाओं जैसे C, Java, Python, आदि के साथ कर सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगेगा।