模板题，真的，有个好的模板非常的重要，真的很有用的。这个东西。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MaxN = 55555; int sum[MaxN << 2]; void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void buildT(int l , int r ,int rt) { if(l == r){ scanf("%d",&sum[rt]); return ; } int m = (l + r) >> 1; buildT(l , m , rt << 1); buildT(m + 1 , r , rt << 1 | 1); PushUp(rt); } void UpDate(int p , int add ,int l ,int r,int rt) { if(l == r){ sum[rt] += add; return; } int m = (l + r) >> 1; if(p <= m) UpDate(p , add ,l , m , rt << 1); else UpDate(p , add , m + 1 , r , rt << 1 | 1); PushUp(rt); } int query(int ll ,int rr ,int l , int r ,int rt) { if(ll <= l && rr >= r) return sum[rt]; int m = (l + r) >> 1; int ret = 0; if(ll <= m) ret += query(ll ,rr , l , m , rt << 1); if(rr > m) ret += query(ll ,rr , m + 1 , r , rt << 1 | 1); return ret; } int main() { int t , c; char d[10]; scanf("%d",&t); for(int i = 1 ; i <= t ; i++){ printf("Case %d:\n",i); int n; scanf("%d",&n); buildT(1 , n , 1); while(~scanf("%s",d)){ if(d[0] == 'E') break; int x , y; scanf("%d%d", &x , &y); if(d[0] == 'Q') printf("%d\n",query(x , y , 1 , n ,1)); if(d[0] == 'S') UpDate(x , -y , 1 , n , 1); if(d[0] == 'A') UpDate(x , y , 1 , n , 1); } } return 0; }