1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <numeric> 6 #include <algorithm> 7 #include <cmath> 8 #include <cctype> 9 #include <string>10 using namespace std;11 12 13 const int N = 50005;14 int C[N];15 16 struct peo {17     int x, v;18 }P[N];19 20 int lowbit (int x) {21     return x & -x;22 }23 24 int sum (int x) {25     int ret = 0;26     while (x > 0) {27         ret += C[x]; x -= lowbit(x);28     }29     return ret;30 }31 32 void add (int x, int d) {33     while (x <= 50000) {34         C[x] += d; x += lowbit(x);35     }36 }37 38 int _sum (int d, int u) {39     return sum(u) - sum(d - 1);40 }41 42 int main () {43     int T, n, cur = 0; scanf("%d", &T);44     char op[10];45     while (T --) {46         memset(C, 0, sizeof(C));47         memset(P, 0, sizeof(P));48         scanf("%d", &n);49         for (int i = 0 ; i < n; ++ i) {50             scanf("%d", &P[i].v);51             P[i].x = i + 1;52             add (P[i].x, P[i].v);53         }54         //cout << sum(3) << endl;55         printf("Case %d:\n", ++ cur);56         while (scanf("%s", op)) {57             if (op[0] == ‘E‘) {58                 break;59             } else if (op[0] == ‘Q‘) {60                 int x, y;61                 scanf("%d %d", &x, &y);62                 cout << _sum(x, y) << endl;63             } else if (op[0] == ‘S‘) {64                 int x, y;65                 scanf("%d %d", &x, &y);66                 add (x, -y);67             } else if (op[0] == ‘A‘) {68                 int x, y;69                 scanf("%d %d", &x, &y);70                 add (x, y);71             }72         }73     }74     return 0;75 }

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cctype> 8 #include <algorithm> 9 #include <numeric>10 11 using namespace std;12 13 struct P{14     int sum, l, r;15 } node[150050];16 17 int n, num[50050] = {0};18 19 void build (int k, int l, int r) {20     node[k].l = l, node[k].r = r;21     if (l == r) {22         node[k].sum = num[l];23     } else {24         build(2 * k, l, (l + r) / 2);25         build(2 * k + 1, ((l + r) / 2) + 1, r);26         node[k].sum = node[2 * k].sum + node[2 * k + 1].sum;27     }28 }29 30 void update(int k, int i, int x) {31     if (node[k].l <= i && node[k].r >= i) {32         node[k].sum += x;33     }34     if (node[k].l == node[k].r) {35         return ;36     }37     if (i <= node[2 * k].r) {38         update(2 * k, i, x);39     }40     else update(2 * k + 1, i, x);41 }42 43 int query (int k, int l, int r) {44     if (l == node[k].l && r == node[k].r) {45         return node[k].sum;46     }47     if (r <= node[2 * k].r)  {48         return query(2 * k, l, r);49     }50     if (l >= node[2 * k + 1].l) {51         return query(2 * k + 1, l, r);52     } else {53         return query(2 * k, l, node[2 * k].r) + query(2 * k + 1, node[2 * k + 1].l, r);54     }55 }56 57 int main(){58     int T;59     scanf("%d",&T);60     for (int z = 1; z <= T; ++ z) {61         memset(num, 0, sizeof(num));62         scanf("%d", &n);63         for (int i = 1; i <= n; ++ i) {64             scanf("%d",&num[i]);65         }66         build(1, 1, n);67         char s[100];68         printf("Case %d:\n",z);69         while (scanf("%s", s)){70             if (s[0] == ‘E‘)    break;71             if (s[0] == ‘Q‘){72                 int a, b;73                 scanf("%d%d" ,&a ,&b);74                 printf("%d\n",query(1, a, b));75             }76             if (s[0] == ‘A‘){77                 int a,x;78                 scanf("%d%d", &a, &x);79                 update(1, a, x);80             }81             if (s[0] == ‘S‘) {82                 int a,x;83                 scanf("%d%d", &a, &x);84                 update(1, a, -x);85             }86         }87     }88     return 0;89 }