यहां, हमें आकार n का एक ऐरे दिया गया है जिसके सभी तत्व प्रारंभ में 0 हैं। और इस पर कुछ क्वेरीज़ की जानी हैं। दो प्रकार की क्वेरीज़ हैं:
update(l, r, value) - इंडेक्स l से r के बीच के ऐरे के तत्वों में value जोड़ें। उदाहरण के लिए,
update(2, 4, 5)इंडेक्स 4 और 5 पर तत्व 2 रखकर ऐरे को अपडेट करेगा।getRangeSum(l, r) - इंडेक्स l से r तक के तत्वों का योग ज्ञात करें। उदाहरण के लिए,
getRangeSum(4, 7)इंडेक्स 4, 5, 6, 7 वाले सभी तत्वों का योग ज्ञात करेगा।
उदाहरण
इनपुट
n = 7, arr[7] = {0,0,0,0,0,0,0}
Q1 = update(3, 6, 4)
Q2 = update(0, 4, 2)
Q3 = Sum(2, 5)
आउटपुट
10
व्याख्या
क्वेरीज़ हल करना:
Q1 - update(3, 6, 4) = {0, 0, 0, 4, 4, 4, 4}
Q2 - update(0, 4, 2) = {2, 2, 2, 2, 2, 4, 4}
Q3 - sum(2, 5) = 2+2+2+4 = 10
इस समस्या को हल करने का एक नाइव दृष्टिकोण प्रत्येक अपडेट क्वेरी पर ऐरे को अपडेट करना और फिर योग ज्ञात करना होगा लेकिन यह इतना प्रभावी नहीं है, इसलिए आइए समस्या को हल करने का एक अधिक प्रभावी दृष्टिकोण सीखें।
आइए अपडेट क्वेरीज़ के योग क्वेरी पर प्रभाव को देखें। योग क्वेरी sum[l,r] के रूप में है, हम इसे sum[0,k] के रूप में विभाजित करेंगे और फिर निचली सीमा के योग को ऊपरी सीमा के योग से घटाएंगे।
sum[l,r] = sum[0,r] - sum[0,l]
तो, sum[0,k] के प्रभाव sum[l,r] पर प्रतिबिंबित होंगे। योग वेरिएबल k अपनी सापेक्ष मान के आधार पर 3 अलग-अलग क्षेत्रों में होगा और अपडेट क्वेरी की रेंज [l,r] में होगा।
क्षेत्र 1 - k, 0 और l के बीच है यानी 0 < k < l
इस मामले में, अपडेट क्वेरी योग क्वेरी को प्रभावित नहीं करेगी।
क्षेत्र 2 - k, l और r के बीच है यानी l ≤ k ≤ r
इस मामले में, योग क्वेरी l से k तक के मानों पर विचार करेगी।
क्षेत्र 3 - k, r से बड़ा है यानी k > r
इस मामले में, योग क्वेरी l से r तक के सभी मानों पर विचार करेगी।
अब, आइए रेंज अपडेट और रेंज क्वेरीज़ को हल करने का प्रोग्राम देखें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getSum(int BITree[], int i) {
int sum = 0;
i++;
while (i > 0) {
sum += BITree[i];
i -= i & (-i);
}
return sum;
}
void updateBITree(int BITree[], int n, int i, int val) {
i = i + 1;
while (i <= n) {
BITree[i] += val;
i += i & (-i);
}
}
void update(int BITTree1[], int BITTree2[], int n, int l, int r, int value) {
updateBITree(BITTree1, n, l, value);
updateBITree(BITTree1, n, r+1, -value);
updateBITree(BITTree2, n, l, value*(l-1));
updateBITree(BITTree2, n, r+1, -value*r);
}
int sum(int x, int BITTree1[], int BITTree2[]) {
return (getSum(BITTree1, x) * x) - getSum(BITTree2, x);
}
int getRangeSum(int l, int r, int BITTree1[], int BITTree2[]) {
return sum(r, BITTree1, BITTree2) - sum(l-1, BITTree1, BITTree2);
}
int* createBITree(int n) {
int* BITree = new int[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;
return BITree;
}
int main() {
int n = 7;
int *BITTree1, *BITTree2;
BITTree1 = createBITree(n);
BITTree2 = createBITree(n);
update(BITTree1, BITTree2, n, 3, 6, 9);
update(BITTree1, BITTree2, n, 0, 4, 5);
cout << "सभी अपडेट क्वेरीज़ लागू करने के बाद योग क्वेरी का आउटपुट है \t"
<< getRangeSum(1, 5, BITTree1, BITTree2);
return 0;
}
आउटपुट
सभी अपडेट क्वेरीज़ लागू करने के बाद योग क्वेरी का आउटपुट है
