一、幾個問題

問題一：已知數組a[],元素個數為n,現在要求a數組中i到j區間內的和(1<=i<=j<=n)

解法1：每次查詢就把i到j之間每個元素都加起來。最壞情況O(Qn)（Q為查詢次數）

解法2：用前綴和數組sum[k]來記錄1到k的和，查詢時，就輸出sum[j]-sum[i-1]。O(1)

問題二：已知數組a[],元素個數為n,現在有兩種操作

1、求a數組中i到j區間內的和(1<=i<=j<=n)

2、將a數組中a[k](1<=k<=n)的值加上d。

解法1：每次查詢就把i到j之間每個元素都加起來，每次更改就把a[k]加上d。最壞情況O(Qn)

解法2：用前綴和數組sum[k]來記錄1到k的和，查詢時，就輸出sum[j]-sum[i-1]，更改時，就把k到n之間的所有元素都加上d。最壞情況O(Qn)

解法3：樹狀數組。O(Qlog(n))

樹狀數組就是在這種背景下產生的。

二、樹狀數組的概念

利用二進制來分類，每一個數存的數據是存的一個區間，它存的區間大小，取決于它的二進制里權值最低的1權值，

如果感覺聽不懂，就來看一下例子吧。

比如說6，轉化成二進制位110，權值最低的1就是紅色標注的那個1，它的權值是2。

再比如說12，轉化成二進制位1100，權值最低的權值就是4。

求它的最低權值有一個簡便算法：

int lowbit(int x)

{

return x&-x;}

接下來就是求和的操作，我們發現1~14之間的和是a[14]+a[12]+a[8]，恰好是14對應二進制a[1110],a[1100],a[1000]

（以上的1110、1100、1000位二進制），于是可以發現求和算法：

int getsum(int x)

{

int sum=0;

while(x){

sum+=treearray[x];

x-=lowbit(x);}}

然后是修改操作，實際上就是找它的父親，直到它的父親大于n為止。

void update(int x,int d)

{

while(x<=n){

treearray[x]+=d;

x+=lowbit(x);}}

有了這三個函數，求解上面的問題就容易多了，但是要注意初始化：for(i=1;i<=n;i++){

scanf("%d",&x);

update(i,x);}

完整代碼：

#include<cstdio>int treearray[1000002],N;int lowbit(int x){    return x&-x;}int getsum(int x){    int sum=0;    while(x){        sum+=treearray[x];        x-=lowbit(x);    }    return sum;}void update(int i,int x){    while(i<=N){        treearray[i]+=x;        i+=lowbit(i);    }}int main(){    int Q,i,a,b,x;    scanf("%d%d",&N,&Q);    for(i=1;i<=Q;i++){        scanf("%d%d%d",&x,&a,&b);        if(x==0){            update(a,b);        }        if(x==1){            PRintf("%d/n",getsum(b)-getsum(a-1));        }    }}