学步园

#include <cstdio>

#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 55555;
int sum[maxn<<2];//x4
void PushUP(int rt) {//区间求和,从叶子节点更新上来
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt) {
	if (l == r) {//线段树是基于数组的,节点一层一层排下来,完全二叉树
		scanf("%d",&sum[rt]);
		return ;
	}//从父节点出发,左儿子和右儿子是通过数组下标找到的
	//而其对应的左端点和右端点是在参数传递的时候同步保存的,不需特别记录
	int m = (l + r) >> 1;//middle
	build(lson);//define的作用!
	build(rson);//总是先调用左儿子,保证叶子节点的建立顺序是从小到大
	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 , lson);
	else update(p , add , rson);
	PushUP(rt);//更新自己
}       //询问区间    扫描区间    子树根节点/当前节点
int query(int L,int R,int l,int r,int rt) {//询问也是递归的
	if (L <= l && r <= R) {//一个节点的特征参数即左右端点和数组下标
		return sum[rt];
	}//如果该节点的管辖区域全在查询区域内,直接返回该节点数据
	int m = (l + r) >> 1;
	int ret = 0;//看所询问区间是否涉及左 or 右儿子;涉及,则递归询问
	if (L <= m) ret += query(L , R , lson);//总能抵达L==l||r==R
	if (R >= m+1) ret += query(L , R , rson);
	return ret;
}
int main() {
	int T , n;
	scanf("%d",&T);
	for (int cas = 1 ; cas <= T ; cas ++) {
		printf("Case %d:\n",cas);
		scanf("%d",&n);
		build(1 , n , 1);//sum数组从1开始
		char op[10];
		while (scanf("%s",op)) {//以空格为分隔符
			if (op[0] == 'E') break;
			int a , b;
			scanf("%d%d",&a,&b);
			if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));
			else if (op[0] == 'S') update(a , -b , 1 , n , 1);
			else update(a , b , 1 , n , 1);
		}
	}
	return 0;
}