Ở đây, chúng ta được cho một mảng kích thước n ban đầu có tất cả các phần tử là 0. Và có một số truy vấn cần thực hiện trên nó. Có hai loại truy vấn:
update(l, r, value) - Thêm giá trị vào các phần tử của mảng nằm giữa 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 tại chỉ số 4 và 5.
getRangeSum(l, r) - Tìm tổng các phần tử trong phạm vi từ l đến r. Ví dụ, getRangeSum(4, 7) sẽ tìm tổng tất cả các phần tử có chỉ số 4, 5, 6, 7.
Hãy xem ví dụ để hiểu bài toá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
Giải các truy vấn: 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 bài toán này, cách tiếp cận đơn giản sẽ là cập nhật mảng tại mỗi truy vấn update và sau đó tìm tổng, nhưng cách này không hiệu quả. Hãy học một cách tiếp cận hiệu quả hơn.
Hãy xem ảnh hưởng của các truy vấn update đến truy vấn sum. Truy vấn sum có dạng sum[l,r], chúng ta sẽ tách thành các truy vấn sum dạng sum[0,k] và sau đó trừ sum đến giới hạn dưới từ sum đến giới hạn trên.
sum[l,r] = sum[0,r] - sum[0,l]
Vì vậy, hiệu ứng của sum[0,k] sẽ phản ánh lên sum[l,r]. Biến sum 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 update.
Vùng 1 - k nằm giữa 0 và l tức là 0 < k < l
Trong trường hợp này, truy vấn update sẽ không ảnh hưởng đến truy vấn sum.
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 sum sẽ tính 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 sum sẽ tính tất cả các giá trị giữa l đến r.
Bây giờ, hãy xem chương trình giải quyết Cập nhật và Truy vấn Phạm vi
//Chương trình giải quyết Cập nhật 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<<"Kết quả truy vấn sum sau khi áp dụng tất cả truy vấn update là \t" <<getRangeSum(1,5,BITTree1,BITTree2); return 0; }Đầu ra
Kết quả truy vấn sum sau khi áp dụng tất cả truy vấn update là