為了更好地使用複雜度比線段樹更加優化的樹狀數組，是以必須實作樹狀數組的區間更新；樹狀數組時間複雜度為O(MlogN)， 實際用的時候優于線段樹，且寫得少。
區間更新、單點查詢
引入差分數組，假設初始資料數組為a，另a[0] = 0；設要維護的差分數組為 d[i] = a[i] - a[i-1]；進一步可知 a[i] = d[1] + d[2] + ... + d[i]; 即前i項和，為友善記為sigma(d, i)；例如如下例子：
a：1 2 3 5 6 9
d：1 1 1 2 1 3
如果進行區間[2, 5]更新加2，則：
a：1 4 5 7 8 9
d：1 3 1 2 1 1
會發現當某個區間[x, y]内值發生了同等改變，但這個區間内的內插補點還是不變的，隻有d[x]和d[y+1]的值發生了改變。
是以可以建立區間更新、單點查詢的樹狀數組去維護d[]，例如如下例子：
d：1 1 1 2 1 3
c：1 2 1 5 1 4（c值如何計算參考下圖）
區間[2, 5]更新加2，則：
d：1 3 1 2 1 1
c：1 4 1 7 1 2（c值如何計算參考下圖）
int lowbit(int k){
return k & -k;
}
void update(int n, int *c, int i, int va){
while(i <= n){
c[i] += va;
i += lowbit(i);
}
}
int pointValue(int *c, int i) {
int res = 0;
while(i > 0){
res += c[i];
i -= lowbit(i);
}
return res;
}
//-------------------------------------
// 在區間[x, y]增加k
updata(n, c, x, k);
updata(n, c, y+1, -k);
// 獲得第i點的值
pointValue(c, i);
區間更新、區間查詢
根據差分數組：
sum[n]
= a[1] + a[2] + .. + a[n];
= sigma(d, 1) + sigma(d, 2) + ... + sigma(d, n);
= n*d[1] + (n-1)*d[2] + ... + 2*d[n-1] + 1*d[n];
= n*(d[1] + d[2] +...+ d[n]) - (0*d[1] + 1*d[2] + ... + (n-1)*d[n]);
是以可以得到 sum[n] =n * sigma(d, n) - (0*d[1] + 1*d[2] + ... + (n-1)*d[n]);
令r[i] = (i-1) * d[i];
則 sum[n] = n * sigma(d, n) - sigma(r, n);
此時則需要構造兩個樹狀數組去分别維護d[]和r[]的更新；例如如下例子：
a： 1 2 3 5 6 9
d： 1 1 1 2 1 3
c1：1 2 1 5 1 4
r： 0 1 2 6 4 15
c2：0 1 2 9 4 19
如果進行區間[2, 5]更新加2，則：
a： 1 4 5 7 8 9
d： 1 3 1 2 1 1
c1：1 4 1 7 1 2
r： 0 3 2 6 4 5
c2：0 3 2 11 4 9
注：c1、c2的計算過程同樣參考上圖。
注意c2更新前後，其在區間左端點2處開始向後更新加k*(2-1)，在右端點5再加1=6處，更新減k*(5-1)。
代碼如下：
int lowbit(int k){
return k & -k;
}
void update(int n, int *c1, int *c2, int i, int va){
int x = i;
while(i <= n){
c1[i] += va;
c2[i] += va * (x-1);
i += lowbit(i);
}
}
int sum(int *c1, int *c2, int i) {
int res = 0, x = i;
while(i > 0){
res += x * c1[i] - c2[i];
i -= lowbit(i);
}
return res;
}
//-------------------------------------
// 在區間[x, y]增加k
updata(n, c, x, k);
updata(n, c, y+1, -k);
// 獲得[x, y]的和
res = sum(c1, c2, y) - sum(c1, c2, x-1);
其它細節可參考：https://www.cnblogs.com/xenny/p/9739600.html