यहां, हमें आकार n की एक सरणी दी गई है जिसमें शुरू में सभी तत्व 0 हैं। और कुछ प्रश्न हैं जो इस पर किए जाने हैं। क्वेरी दो प्रकार की होती हैं -
-
अपडेट करें(l,r, value) - सरणी के उन तत्वों में मान जोड़ें जो सूचकांक l से r के बीच हैं। उदाहरण के लिए, अपडेट (2, 4, 5) एलिमेंट 2 को इंडेक्स 4 और 5 पर एलिमेंट पर रखकर ऐरे को अपडेट करेगा।
-
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
स्पष्टीकरण
Solving queries: 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 इस समस्या को हल करने के लिए प्रत्येक अद्यतन क्वेरी पर सरणी को अद्यतन करने और फिर योग खोजने के लिए एक सरल दृष्टिकोण होगा लेकिन यह इतना प्रभावी नहीं है तो आइए समस्या को हल करने के लिए एक अधिक प्रभावी दृष्टिकोण सीखें।
आइए देखें कि सम क्वेरी पर अद्यतन प्रश्नों का प्रभाव क्या है। सम क्वेरी फॉर्म योग का है [एल, आर], हम इसे फॉर्म योग [0, के] के योग प्रश्नों में विभाजित करेंगे और फिर योग को योग से निचली सीमा से निचली सीमा तक घटा देंगे।
sum[l,r] = sum[0,r] - sum[0,l]
तो, राशि का प्रभाव [0, k] योग [l, r] पर परिलक्षित होगा। योग चर k अपने सापेक्ष मूल्य के आधार पर 3 अलग-अलग क्षेत्रों में स्थित होगा और अद्यतन क्वेरी की [l,r] श्रेणी में होगा।
क्षेत्र 1 − k, o और l के बीच स्थित है अर्थात 0
इस मामले में, अद्यतन क्वेरी योग क्वेरी को प्रभावित नहीं करेगी।
क्षेत्र 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<<"The output of sum query after applying all update queries is \t" <<getRangeSum(1,5,BITTree1,BITTree2);
return 0;
} आउटपुट
The output of sum query after applying all update queries is