题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1166
AC代码
#include<iostream> #include<string> #include <algorithm> #include<cstring> #include<cstdio> using namespace std; typedef long long ll; const int N = 1e5 + 5; struct node { int l,r; int nSum; }tree[N*3]; int a[N]; void Build(int i, int l, int r) { tree[i].l = l; tree[i].r = r; if (l == r) { tree[i].nSum = a[l]; return; } int mid = (l+r) >> 1; Build(i<<1, l, mid); Build(i<<1|1, mid +1, r); tree[i].nSum = tree[i<<1].nSum + tree[i<<1|1].nSum; } void Add(int i, int j, int c) { tree[i].nSum += c; if (tree[i].l == tree[i].r && tree[i].l == j) { return; } int mid = (tree[i].l + tree[i].r) >> 1; if (j <= mid) Add(i<<1, j,c); else if (j > mid) Add(i << 1|1, j ,c); } void Sub(int i, int j, int c) { tree[i].nSum -= c; if (tree[i].l == tree[i].r && tree[i].l == j) { return; } int mid = (tree[i].l + tree[i].r) >> 1; if (j <= mid) Sub(i<<1, j,c); else if (j > mid) Sub(i << 1|1, j ,c); } int Query(int i, int a, int b) { if (a == tree[i].l && b == tree[i].r) { return tree[i].nSum; } int mid = (tree[i].l + tree[i].r) >> 1; if (b <= mid) Query(i<<1, a, b); else if(a > mid) Query(i<<1|1, a, b); else { return Query(i<<1,a,mid)+Query(i<<1|1, mid + 1, b); } } int main() { // ios::sync_with_stdio(false);cin.tie(NULL); int t; scai(t); for (int _ = 1; _ <= t; _++){ printf("Case %d:\n", _); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } Build(1,1,n); char s[20]; while(1){ scanf("%s", s); int t1, t2; if (strcmp(s, "Query") == 0) { scai(t1); scai(t2); printf("%d\n", Query(1,t1,t2)); } else if (strcmp(s, "Add") == 0) { scai(t1); scai(t2); Add(1,t1,t2); } else if (strcmp(s, "Sub") == 0) { scai(t1); scai(t2); Add(1,t1,-t2); } else if (strcmp(s, "End") == 0) { break; } } } }