http://lightoj.com/volume_showproblem.php?problem=1112
题目大意：
1 i 将第i个数值输出，并将第i个值清0
2 i v 将第i个数值加v
3 i j 输出从i到j的数值和
简单的单点更新+区间求和，代码很简单的模板
但此题有一个神坑的地方当操作为1是输出第i个数值不是直接输出，而是通过查找输出(太坑了。。。)
#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #define N 100010 #define Lson root<<1, L, tree[root].Mid() #define Rson root<<1|1, tree[root].Mid() + 1, R using namespace std; struct Tree { int L, R; long long sum, e; bool op; int Mid() { return (R + L) / 2; } } tree[N * 4]; long long al[N]; void Build(int root, int L, int R) { tree[root].L = L, tree[root].R = R; tree[root].op = false; if(L == R) { tree[root].sum = al[L]; return ; } Build(Lson); Build(Rson); tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; } void Insert(int root, int k, long long e) { tree[root].sum += e; if(tree[root].L == tree[root].R) return ; if(k <= tree[root].Mid()) Insert(root<<1, k, e); else if(k > tree[root].Mid()) Insert(root<<1|1, k, e); } long long Query(int root, int L, int R) { if(tree[root].L == L && tree[root].R == R) return tree[root].sum; if(R <= tree[root].Mid()) return Query(root<<1, L, R); else if(L > tree[root].Mid()) return Query(root<<1|1, L, R); else return Query(Lson) + Query(Rson); } int main() { int m, n, a, p, b, i, t, x = 0; long long e; char s[10]; scanf("%d", &t); while(t--) { x++; scanf("%d%d", &m, &n); for(i = 1 ; i <= m ; i++) scanf("%lld", &al[i]); Build(1, 1, m); printf("Case %d: ", x); while(n--) { scanf("%d", &p); if(p == 1) { scanf("%d", &a); printf("%d ", Query(1, a + 1, a + 1));//注意! ! ! 坑来了！！！ Insert(1, a + 1, -Query(1, a + 1, a + 1));//此处一样 } else if(p == 2) { scanf("%d%d", &a, &b); Insert(1, a + 1, b); } else if(p == 3) { scanf("%d%d", &a, &b); printf("%lld ", Query(1, a + 1, b + 1)); } } } return 0; }