關於樹狀數組的模板，樹狀數組模板

關於樹狀數組的模板，樹狀數組模板

樹狀數組在只是單點添加和區間求和的過程中實用效率遠大於線段樹，所以有必要學習一下（個人見解）

lowbit：i&（-i）

對於單點添加直接使用add就可以完成，如果還有別的操作還可以再另寫函數。

對於求和可以直接用 sum_max  減去  sum_min-1 就可以求出區間和比、代碼復雜度遠低於線段樹。

以洛谷3374為例：http://daniu.luogu.org/problem/show?pid=3374#sub

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 using namespace std;
 5 #define MAX 500000
 6 int N,M;
 7 int a[MAX],c[MAX];
 8 //======================================================
 9 void init();//
10 void ADD(int ,int );//
11 int sum(int );
12 //======================================================
13 void ADD(int x,int y)
14 {
15    for(int i=x;i<=N;i+=i&(-i)  ){
16       c[i]+=y;
17    }
18 }
19 //======================================================
20 int sum(int x)
21 {
22    int SUM=0;
23    for(int i=x;i>=1;i-=i&(-i))
24       SUM+=c[i];
25    return SUM;
26 }
27 //======================================================
28 void init()
29 {
30    int aa,bb,cc;
31    cin>>N>>M;
32    for(int i=1;i<=N;i++){
33       cin>>a[i];
34       ADD( i , a[i] );
35    }
36    for(int i=1;i<=M;i++){
37       cin>>aa>>bb>>cc;
38       if(aa==1)ADD(bb,cc);
39       if(aa==2)cout<<sum(cc)-sum(bb-1)<<endl;
40    }
41 }
42 //======================================================
43 int main()
44 {
45   init();
46    return 0 ;
47 }