여기에서는 처음에 모든 요소가 0인 크기 n의 배열이 제공됩니다. 여기에 수행해야 하는 몇 가지 쿼리가 있습니다. 쿼리에는 두 가지 유형이 있습니다 -
-
업데이트(l,r, 값) - 인덱스 l에서 r 사이에 있는 배열의 요소에 값을 추가합니다. 예를 들어, 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
설명
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 이 문제를 해결하기 위해 순진한 접근 방식은 각 업데이트 쿼리에서 배열을 업데이트한 다음 합계를 찾는 것이지만 이것은 그다지 효과적이지 않으므로 문제를 해결하는 더 효과적인 접근 방식을 알아보겠습니다.
업데이트 쿼리가 합계 쿼리에 미치는 영향을 살펴보겠습니다. 합계 쿼리는 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는 o와 l 사이에 있습니다. 즉, 0
이 경우 업데이트 쿼리는 합계 쿼리에 영향을 미치지 않습니다.
지역 2 − k는 l과 r 사이에 있습니다. 즉, l ≤ k ≤ r
이 경우 합계 쿼리는 l에서 k까지의 값을 포함합니다.
지역 3 - k는 r보다 큽니다. 즉, k>r
이 경우 합계 쿼리는 l에서 r 사이의 모든 값을 포함합니다.
이제 Range Update 및 Range 쿼리를 해결하는 프로그램을 살펴보겠습니다.
//범위 업데이트 및 범위 쿼리를 해결하는 프로그램예시
#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