题目描述：
已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
这道题看名字就知道是树状数组的模板题，但是菜鸡的我想熟悉线段树，所以用了线段树。
思路没有什么好说的(如果不知道怎么做的，建议先学习树状数组)，详情看代码。
一些小细节：
1.运算都用位运算加速
2.不要用cin,cout，亲测超时
3.对于根node，
左儿子 是 node * 2 ---->> node << 1;
右儿子是 node * 2 + 1 ---->> node<<1 | 1;
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int N = 5e5 + 10; 5 6 int n, m; 7 int tree[N*4]; 8 9 10 //不用建树，因为你会发现代码是一样的。。。亲测 11 12 //在pos上加上X 13 void update(int node, int l, int r, int pos, int x) 14 { 15 if(l == r) {tree[node] += x; return;} 16 int mid = (l + r) >> 1; 17 if(mid >= pos) update(node<<1, l, mid, pos, x); 18 else update((node<<1)|1, mid+1, r, pos, x); 19 tree[node] = tree[node<<1] + tree[(node<<1)+1]; 20 } 21 22 //查询区间[L, R]的和 23 int query(int node, int l, int r, int L, int R) 24 { 25 if(L > r || R < l) return 0; 26 if(L <= l && R >= r) return tree[node]; 27 int mid = (l + r) >> 1; 28 return query(node<<1, l, mid, L, R) + query((node<<1)|1, mid+1, r, L, R); 29 } 30 31 int main() 32 { 33 scanf("%d %d", &n, &m); 34 for(int i = 1; i <= n; i++) 35 { 36 int x; 37 scanf("%d", &x); 38 update(1, 1, N, i, x); 39 } 40 for(int i = 0; i < m; i++) 41 { 42 int op, x, y; 43 scanf("%d %d %d", &op, &x, &y); 44 if(op == 1) update(1, 1, N, x, y); 45 else printf("%d\n", query(1, 1, N, x, y)); 46 } 47 return 0; 48 }