线段树区间求和 //#pragma comment(linker, "/STACK:1024000000,1024000000") #include <iostream> #include <stack> #include <queue> #include <cstdio> #include <cstdlib> #include <cmath> #include <set> #include <vector> #include <cstring> #include <algorithm> #define INF 0x3fffffff #define N 50010 #define M (N << 2) #define LL long long #define mod 95041567 using namespace std; struct Node{ int val; int sum; }; int p[M]; void build(int rt, int l, int r){ if(l == r){ scanf("%d", &p[rt]); return ; } int mid = (r - l) / 2 + l; int lc = rt << 1; int rc = lc + 1; build(lc, l, mid); build(rc, mid + 1, r); p[rt] = p[lc] + p[rc]; } void update(int rt, int l, int r, int pos, int val){ if(l == r) { p[rt] += val; return ; } int mid = (r - l)/ 2 + l; int lc = rt << 1; int rc =lc + 1; if(pos <= mid) update(lc, l, mid, pos, val); else update(rc, mid + 1, r, pos, val); p[rt] = p[lc] + p[rc]; } void query(int rt, int l, int r, int L, int R, int &val){ if(l == L && r == R){ val += p[rt]; return ; } int mid = (r - l) / 2 + l; int lc = rt << 1; int rc = lc + 1; if(L > mid) query(rc, mid + 1, r, L, R, val); else if(R <= mid) query(lc, l, mid, L, R, val); else { query(lc, l, mid, L, mid, val); query(rc, mid + 1, r, mid + 1, R, val); } } int main() { // freopen("in.txt", "r", stdin); int t, cnt = 0; scanf("%d", &t); while(t --){ printf("Case %d:\n", ++ cnt); int n; scanf("%d", &n); build(1, 1, n); while(1){ char s[10]; scanf("%s", s); if(s[0] == 'E') break; int i, j; scanf("%d %d", &i, &j); if(s[0] == 'Q') { int val = 0; query(1, 1, n, i, j, val); printf("%d\n", val); } else { if(s[0] == 'S') j = -j; update(1, 1, n, i, j); } } } return 0; }