Ở đây, chúng ta được cung cấp một mảng kích thước n mà ban đầu có tất cả các phần tử bằng 0. Và có một số truy vấn sẽ được thực hiện trên đó. Có hai loại truy vấn -
-
cập nhật (l, r, value) - Thêm giá trị cho các phần tử của mảng nằm trong khoảng từ chỉ số l đến r. Ví dụ:update (2, 4, 5) sẽ cập nhật mảng bằng cách đặt phần tử 2 vào phần tử ở chỉ mục 4 và 5.
-
getRangeSum (l, r) - Tìm tổng các phần tử trong dãy phần tử từ l đến r. Ví dụ:getRangeSum (4, 7) sẽ tìm tổng của tất cả các phần tử có chỉ số 4, 5, 6, 7.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
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) Đầu ra
10
Giải thích
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 Để giải quyết vấn đề này, một cách tiếp cận đơn giản sẽ là cập nhật mảng ở mỗi truy vấn cập nhật và sau đó tìm tổng nhưng cách này không hiệu quả lắm, vì vậy chúng ta hãy tìm hiểu một cách tiếp cận hiệu quả hơn để giải quyết vấn đề.
Hãy xem ảnh hưởng của các truy vấn cập nhật đối với truy vấn tổng. Truy vấn tổng có dạng sum [l, r], chúng tôi sẽ chia nó thành các truy vấn tổng có dạng sum [0, k] và sau đó trừ tổng đến giới hạn dưới từ tổng đến giới hạn dưới.
sum[l,r] = sum[0,r] - sum[0,l]
Vì vậy, ảnh hưởng của tổng [0, k] sẽ được phản ánh trên tổng [l, r]. Biến tổng k sẽ nằm trong 3 vùng khác nhau dựa trên giá trị tương đối của nó và sẽ nằm trong phạm vi [l, r] của truy vấn cập nhật.
Vùng 1 - k nằm giữa o và l, tức là 0
Trong trường hợp này, truy vấn cập nhật sẽ không ảnh hưởng đến truy vấn tổng.
Vùng 2 - k nằm giữa l và r tức là l ≤ k ≤ r
Trong trường hợp này, truy vấn tổng sẽ giải trí các giá trị từ l đến k.
Vùng 3 - k lớn hơn r tức là k> r
Trong trường hợp này, truy vấn tổng sẽ giải thích tất cả các giá trị từ l đến r.
Bây giờ, chúng ta hãy xem chương trình giải quyết Cập nhật phạm vi và Truy vấn phạm vi
// Chương trình giải quyết vấn đề cập nhật phạm vi và truy vấn phạm vi Ví dụ
#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;
} Đầu ra
The output of sum query after applying all update queries is