树状数组入门（求和）

Description

输入一个数列A1,A2….An(1<=N<=100000)，在数列上进行M(1<=M<=100000)次操作，操作有以下两种：
(1)格式为C I X，其中C为字符"C"，I和X(1<=I<=N,|X|<=10000)都是整数，表示把把a[I]改为X
(2)格式为Q L R，其中Q为字符"Q"，L和R表示询问区间为[L,R](1<=L<=R<=N)，表示询问A[L]+…+A[R]的值。

Input

第一行输入N(1<=N<=100000)，表述数列的长度，接下来N行，每行一个整数(绝对值不超过10000)依次输入每个数
；接下来输入一个整数M(1<=M<=100000)，表示操作数量，接下来M行，每行为C I X或者Q L R。

Output

对于每个Q L R 的操作输出答案。

Sample Input

5
1
2
3
4
5
3
Q 2 3
C 3 9
Q 1 4

Sample Output

5
16

图大家自己上网找，这里解释树状数组的构造

假如有两个数组,其中一个是a数组,另一个是树状数组t数组

树状数组类似前缀和，但是效率要高得多

首先，我给大家列举一下：c[i]初始等于a[i]

t[1]=a[1],t[2]=t[1]+a[2],t[3]=a[3],t[4]=t[2]+t[3],t[5]=a[5],t[6]=t[2]+a[6],t[7]=a[7],t[8]=t[7]+t[6]+t[4];

然后大家可以发现一个规律，树状数组t后缀为奇数就是数组a中的本身，转成二进制后就很直观了

就拿8举个例子，8转成二进制后是1000

k代表的是转成二进制之后的出现0的位置，二进制最右一位是2^0，那么我们可以发现（n=8）n-2^k恰好就是t数组加上的

就像8二进制第一个出现0的位置是第0个，那么n-2^0=8-1=7，t[8]确实加了t[7]。

这是不是偶然呢？显然是不可能的，不信我们继续看，8二进制第二个0出现在第1个位置，那么n-2^1=8-2=6，t[8]也确实加了t[6]，这样一来n-2^2=8-4=4,0走完了，t[8]也加完了，这个是真实存在的现象，然后也会很好记忆，如果还有疑惑可以自己去推其他的

下面给出此题代码：

 #include<bits/stdc++.h>
 using namespace std;
 int maxn=100010;
 int n,m;int a[100010];
 int c[100010];
 char s[2];
 int lowbit(int p)
 {
     return (p&(-p));
 }
 void add(int p,int num)
 {
     while (p<=n)
     {
         c[p]+=num;
         p+=lowbit(p);
     }
     return;
 }
 int query(int p)
 {
     int tmp=0;
     while (p)   
     {   
         tmp+=c[p];      
         p-=lowbit(p);   
     }   
     return tmp;
 }
 int main()
 {   
     scanf("%d",&n);             
     for (int i=1;i<=n;i++)       
     {           
         scanf("%d",&a[i]);          
         add(i,a[i]);        
     }       
     scanf("%d",&m);     
     for(int i=1;i<=m;i++)        
     {       
         scanf("%s",s);          
         if (s[0]=='C')          
         {           
             int j,k;                
             scanf("%d%d",&j,&k);                
             add(j,k-a[j]);              
             a[j]=k; 
         }
         else           
         {           
             int l,r;            
             scanf("%d%d",&l,&r);                
             int sum=query(r)-query(l-1);                
             printf("%d
",sum);         
         }       
     }   
     return 0;
 }