資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學二進位制索引樹：C++ 中的區間更新和區間查詢
這裡，我們得到一個大小為 n 的陣列，它最初所有元素都為 0。並且需要對其執行一些查詢。
update(l,r, value) − 將值新增到陣列中索引 l 到 r 之間的元素。例如，update(2, 4, 5) 將更新陣列，在索引 4 和 5 的元素上分別加上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要解決這個問題，一種簡單的辦法是在每個更新查詢中更新陣列，然後求和，但這效率不高，所以讓我們學習一種更有效的解決方法。
讓我們看看更新查詢對求和查詢的影響。求和查詢的形式為 sum[l,r]，我們將把它分成 sum[0,k] 形式的求和查詢，然後從下限的和中減去下限的和。
sum[l,r] = sum[0,r] - sum[0,l]
因此，sum[0,k] 的影響將反映在 sum[l,r] 上。sum 變數 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<<"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
更新於：2020年7月17日
326 次瀏覽
廣告