P3374 【模板】树状数组 1
题目链接：
题目：
如题，已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3个整数，表示一个操作，具体如下：
操作1： 格式：1 x k 含义：将第x个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入 #1
5 51 5 4 2 31 1 32 2 51 3 -11 4 22 1 4
输出 #1
1416
说明/提示
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
样例说明：
故输出结果14、16
//// Created by hanjinyu on 19-9-2.//#includeusing namespace std;typedef long long ll;const int maxn=1e6+10;int n,m;int ans;int input[maxn];struct Node{ int left; int right; int num;}tree[maxn*4];void PushUp(int index){ tree[index].num = tree[index<<1].num+tree[index<<1|1].num;}void build(int l,int r,int index){ tree[index].left=l; tree[index].right=r; if(l==r) { tree[index].num = input[l]; return; } int mid=(l+r)>>1; build(l,mid,index<<1); build(mid+1,r,index<<1|1); PushUp(index);}void change(int index,int dis,int k){ if(tree[index].left==tree[index].right) { tree[index].num += k; return; } if(dis<=tree[index<<1].right) change(index<<1,dis,k); else change(index<<1|1, dis, k); PushUp(index);}void search(int index,int l,int r){ if(l<=tree[index].left&&r>=tree[index].right) { ans+=tree[index].num; return; } if(tree[index<<1].right>=l) search(index<<1,l,r); if(tree[index<<1|1].left<=r) search(index<<1|1,l,r);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&input[i]); } build(1,n,1); int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); if(x==1) change(1,y,z); else if(x==2) { ans=0; search(1,y,z); printf("%d\n",ans); } } return 0;}