题目描述
如题，已知一个数列，你需要进行下面两种操作：
-
将某一个数加上 xx
-
求出某区间每一个数的和
输入格式
第一行包含两个正整数 n,mn,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 mm 行每行包含 33 个整数，表示一个操作，具体如下：
-
1 x k含义：将第 xx 个数加上 kk -
2 x y含义：输出区间 [x,y][x,y] 内每个数的和
输出格式
输出包含若干行整数，即为所有操作 22 的结果。
输入输出样例
输入 #1
5 5 1 5 4 2 3 1 1 3 2 2 5 1 3 -1 1 4 2 2 1 4
输出 #1
14 16
说明/提示
【数据范围】
对于 30\%30% 的数据，1 le n le 81≤n≤8，1le m le 101≤m≤10；
对于 70\%70% 的数据，1le n,m le 10^41≤n,m≤104；
对于 100\%100% 的数据，1le n,m le 5 imes 10^51≤n,m≤5×105。
样例说明：
故输出结果14、16
打算靠洛谷的模板题恢复一下
树状数组就是把一列数组利用其二进制的特点弄成一棵树 通过上面的图可以看出每一个数统计的是最后一个1及后面的0加起来的长度，可以理解为带宽。比如10二进制1010，统计的就是10(二进制)的长度，12的二进制是1100，统计的就是100(二进制)的长度，也就是说 在树状数组中，找到最后一个1和后面的0很重要。向上找父节点就是在最后一个1上加1，求前n项的和就是不断的去掉最后的1。在上一篇文章中我们知道负数在计算机中是按照补码存放的，负数的补码就是取反再加1 ，所以可以发现 (i&-i) 就能取出最后一个1和后面的0 。
显然，树状数组求前N项和的时间复杂度为O(lbN)
此段程序是执行树状数组的单点修改，区间查询
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=500005; 4 typedef long long LL; 5 int n,m; 6 LL a[MAX],c[MAX]; 7 void add(int x,int y){for (;x<MAX;x+=(x&-x)) c[x]+=y;} 8 LL sum(int x){LL an=0;for (;x>0;x-=(x&-x)) an+=c[x];return an;} 9 int main(){ 10 freopen ("tree.in","r",stdin); 11 freopen ("tree.out","w",stdout); 12 int i,j,x,y,z; 13 scanf("%d%d",&n,&m); 14 for (i=1;i<=n;i++) {scanf("%lld",a+i);add(i,a[i]);} 15 for (i=1;i<=m;i++){ 16 scanf("%d%d%d",&x,&y,&z); 17 if (x==1) add(y,z); 18 else printf("%lld ",sum(z)-sum(y-1)); 19 } 20 return 0; 21 }
树状数组还可以进行区间插入，区间查询。
一般来说树状数组只可进行单点操作，得益于树状数组的区间查询是能将1~n全部扫一遍，所以可以通过在区间[x,y]两个端点设卡（及在x处加k，在y+1处-k）这样的单点操作在统计的时候达到区间插入的目的。 以后如果遇到单点修改解决区间问题可以考虑这种方法。
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=500005; 5 int n,m; 6 LL a[MAX],c[MAX];//c[x]用于记录区间操作 7 void add(LL x,LL y){for (;x<MAX;c[x]+=y,x+=(x&-x));} 8 LL search(LL x){LL an=0;for (;x>0;an+=c[x],x-=(x&-x));return an;} 9 int main(){ 10 freopen ("tree.in","r",stdin); 11 freopen ("tree.out","w",stdout); 12 int i,j;LL x,y,k,w; 13 scanf("%d%d",&n,&m); 14 for (i=1;i<=n;i++) scanf("%d",a+i); 15 while (m--){ 16 scanf("%lld",&w); 17 if (w==2){ 18 scanf("%lld",&x); 19 printf("%lld ",a[x]+search(x)); 20 } 21 else { 22 scanf("%lld%lld%lld",&x,&y,&k); 23 add(x,k);add(y+1,-k); 24 } 25 } 26 return 0; 27 }