Chapter 2. 資料結構 樹狀數組
Sylvia's I. 樹狀數組（二叉索引樹）.
動态連續和查詢問題.給定一個數組含有n個元素的數組A，設計一個資料結構，支援以下兩個操作
add（x,d）：讓Ax增加d.
query（L,R）：計算區間[l,r]中所有元素的和
lowbit:我們定義的lowbit(x)是x的二進制表達式中最右邊的1所對應的值，例如，324的二進制是101000100，是以lowbit(324)=4（二進制是100），在程式中實作是lowbit=x&(-x),-x實際上是x的按位取反，末尾加1的結果，如
324=101000100
-324=010111100
按位取“與”後，前面的部分全部變成0，而之後的“100”不變，即lowbit（324）=4
BIT：下圖是一棵典型的BIT，由13個結點組成，編号1—13，而左邊的1、2、4、8是同行結點的lowbit，每一行的結點的lowbit相同
對于結點i，如果它是左子結點，那麼它的父節點編号是i+lowbit（i），如果它是右子節點，那麼它的父節點是i-lowbit（i）
圖1
黑色的結點是BIT中的結點，然後構造一個輔助數組C
Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+..+Ai
換句話說，C數組的每個元素就是A數組中的一段連續和，即圖中紫色+黑色的長條，對于lowbit=1的結點僅指黑色的長條，這個長條中的數的和就是Ci，比如，其中結點4的長條就是從1—4結點，即C4=A1+A2+A3+A4
那麼對于add（x,d）操作，如果修改了Ai，那麼需要從Ci開始往右上走，沿途修改所有包含Ai值的Ci，如下圖，那麼可以看作我們修改的Ci值是左子結點，是以向右上走即可以用i+lowbit(i)計算，如下圖中C3-->C3+lowbit(3)=C3+1=C4-->C4+loebit(4)=C8
代碼：時間複雜度O（logn）
void add(int x,int y){
while (x<=n){
c[x]+=y;
x+=lowbit(x);
}
} 而對于query（l,r）這一操作，先計算字首和Si，從結點i向左上走，把沿途經過的Ci全部加起來，如下圖，此時Ci可以看作右子結點，那麼向左上走可以用i-lowbit（i）計算，然後query（l，r）=Sr-Sl-1
代碼：時間複雜度O（logn）
int sum (int x){
int ret=0;
while (x>0){
ret+=c[x];
x-=lowbit(x);
}
return ret;
} Sylvia's II . 樹狀數組的應用.
① 單點修改和區間求和：
已知一個數列，你需要進行下面兩種操作：
1.将某一個數加上x
2.求出某區間所有數的和
操作1： 格式：1 x k 含義：将第x個數加上k
操作2： 格式：2 x y 含義：輸出區間[x,y]内每個數的和
輸出每一個操作2後的結果
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 500005
int c[MAX];
int n,m,z,t,a,b;
int lowbit(int x){
return (x&(-x));
}
int query (int x){//查詢
int ret=0;
while (x>0){
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int y){//修改，把Ax增加y
while (x<=n){
c[x]+=y;
x+=lowbit(x);
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&z);
add(i,z);//預處理
}
for (int i=1;i<=m;i++){
scanf("%d%d%d",&t,&a,&b);
if (t==1){
add(a,b);//如果是1操作，那麼進行修改
}
else {
printf("%d\n",query(b)-query(a-1));//如果是2操作，那麼輸出區間[a，b]中所有元素的和，它等于字首和Sb-Sa-1
}
}
return 0;
} ②區間修改和單點求值：
已知一個數列，你需要進行下面兩種操作：
1.将某區間每一個數數加上x
2.求出某一個數的值
操作1： 格式：1 x y k 含義：将區間[x,y]内每個數加上k
操作2： 格式：2 x 含義：輸出第x個數的值
輸出每一個操作2後的結果
思想：對于讀入資料進行差分的預處理儲存在C數組中，那麼字首和Si就是Ai.
例如：
5 5
1 5 4 2 3
1 2 4 2
2 3
那麼進行預處理後的數組C是 {1,4，-1，-2,1}
讀入 1 2 4 2 那麼将A數組區間[2,4]都加上2，對于C數組，進行add（2，2）和add（5，-2），C數組變成{1，6，-1，-2，-1}，那麼數組A（代碼中未使用）會變成{1,7,6，4,3}，這就實作了區間[2,4]的數值增加.
讀入 2 3 那麼進行query（3），求C3的字首和就是6也就是A數組中的數值 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 500005
int c[MAX];
int n,m,z,t,pre=0,a,b,d;
int lowbit(int x){
return (x&(-x));
}
int query (int x){//查詢
int ret=0;
while (x>0){
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int y){//修改，把Ax增加y
while (x<=n){
c[x]+=y;
x+=lowbit(x);
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&z);
add(i,z-pre);//使用差分
pre=z;
}
for (int i=1;i<=m;i++){
scanf("%d",&t);
if (t==1){
scanf("%d%d%d",&a,&b,&d);
add(a,d);//對于差分後的數組區間第一個元素加上d，那麼對于原數組在第一個元素之後的每一個值都增加了d
add(b+1,-d);//是以将區間之後的第一個元素減掉d，那麼區間後的元素不受其影響，最終對于原數組隻有區間中的每一個元素都增加了d
}
else {
scanf("%d",&a);
printf("%d\n",query(a));//差分後的數組c的字首和Sa就是原數組Aa的值，直接輸出
}
}
return 0;
}
魚麗之宴
木心
很多人的失落
是違背了自己少年時的立志
自以為成熟，自以為練達，自以為精明
從前多幼稚
總算看透了，想穿了
于是
我們從此變成了自己年少時最憎惡的那種人
Sylvia
二零一七年五月九日
轉載于:https://www.cnblogs.com/jasmine-lee/p/6832793.html