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 }
