0017：【模板】樹狀數組
題目鏈接：//www.luogu.com.cn/problem/P3374
題目描述：
已知一個數列，你需要進行下面兩種操作：
1.將某一個數加上 x
2.求出某區間每一個數的和
看到這道題，首先想到的是直接數組模擬。
不用多說了吧？是人都會。
但是數組模擬求區間和的單次時間複雜度是O（n），本題的數據範圍最大是（5*10^5）^2，很容易爆掉。（本題只有70分）
那麼就要介紹一下這次的演算法——樹狀數組了。
樹狀數組或二叉索引樹，最早由Peter M. Fenwick於1994年以A New Data Structure for Cumulative Frequency Tables為題發表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決數據壓縮里的累積頻率（Cumulative Frequency）的計算問題，現多用於高效計算數列的前綴和， 區間和。
——摘自百度
說白了就是能讓區間和計算變快的演算法。我畫個圖演示一下大概的思想。
C1=A1
C2=A1+A2
C3=A3
C4=A1+A2+A3+A4
C5=A5
C6=A5+A6
C7=A7
C8=A1+A2+A3+A4+A5+A6+A7+A8
C數組就是像樹一樣將A數組的區間聯繫起來的樹狀數組。
那麼如何用C數組找到A數組呢？
這就用到一條神奇的語句：
int lowbit(int x){ return x&(-x); }
大家可以自行上c++模擬一下。
上程式碼：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int A[500005],C[500005]; 4 int n,m,i,j,a,b,c; 5 int lowbit(int x){//實現A數組與C數組的轉換 6 return x&(-x); 7 } 8 void add(int w,int k){//將序列內某個元素加上k 9 while(w<=n){//將每個C數組中包含此元素的元素都加上k 10 C[w]+=k; 11 w+=lowbit(w); 12 } 13 } 14 int Q(int x){//從A1到Ax的區間和，用C數組求 15 int we=0; 16 while(x>0){ 17 we+=C[x]; 18 x-=lowbit(x);//從x搜索，找出之前不包含A1~Ax的元素 19 } 20 return we; 21 } 22 int main(){ 23 cin>>n>>m; 24 for(i=1;i<=n;i++){ 25 scanf("%d",&A[i]); 26 add(i,A[i]); 27 } 28 for(i=0;i<m;i++){ 29 scanf("%d",&a); 30 if(a==1){ 31 scanf("%d%d",&b,&c); 32 add(b,c); 33 }else{ 34 scanf("%d%d",&b,&c); 35 cout<<Q(c)-Q(b-1)<<endl; 36 } 37 } 38 }
