HOJ 1166 敌兵布阵（线段树，点修改区间查询）

线段树，点修改区间查询
本题要点：
1、套用 线段树模板，使用延迟标记 add. 某点减去值 d, 相当于加上 -d;

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 50010;
int a[MaxN];
int T, n;
char cmd[10];struct segTree
{
    int l, r;long long sum, add;
}tree[MaxN * 4];void build(int p, int l, int r)
{
    tree[p].l = l, tree[p].r = r;if(l == r){
    tree[p].sum = a[l], tree[p].add = 0;return;}int mid = (l + r) / 2;build(2 * p, l, mid);build(2 * p + 1, mid + 1, r);tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}void spread(int p)
{
    if(tree[p].add){
    tree[p * 2].sum += tree[p].add * (tree[p * 2].r - tree[p * 2].l + 1);tree[p * 2 + 1].sum += tree[p].add * (tree[p * 2 + 1].r - tree[p * 2 + 1].l + 1);tree[p * 2].add += tree[p].add;     //给左孩子打上延迟标记tree[p * 2 + 1].add += tree[p].add; //给右孩子打上延迟标记tree[p].add = 0; }
}// p是当前节点的编号，
void change(int p, int l, int r, int d, int x)
{
    if(l == r){
    tree[p].sum += d;return;}spread(p);int mid = (l + r) / 2;if(x <= mid){
    change(p * 2, l, mid, d, x);	}else{
    change(p * 2 + 1, mid + 1, r, d, x);	}tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
}long long ask(int p, int l, int r)
{
    if(l <= tree[p].l && r >= tree[p].r){
    return tree[p].sum;}spread(p);int mid = (tree[p].l + tree[p].r) / 2;long long val = 0;if(l <= mid)val += ask(p * 2, l, r);if(r > mid)val += ask(p * 2 + 1, l, r);return val;
}int main()
{
    int x, y;scanf("%d", &T);for(int t = 1; t <= T; ++t){
    scanf("%d", &n);for(int i = 1; i <= n; ++i){
    scanf("%d", &a[i]);}build(1, 1, n);printf("Case %d:\n", t);while(1){
    scanf("%s", cmd);if(cmd[0] == 'E')	break;else if(cmd[0] == 'A'){
    		//加上scanf("%d%d", &x, &y);change(1, 1, n, y, x);}else if(cmd[0] == 'S'){
    	// 减去scanf("%d%d", &x, &y);change(1, 1, n, -y, x);}else{
    	// 查询scanf("%d%d", &x, &y);printf("%lld\n", ask(1, x, y));}}}return 0;
}/* 1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End *//* Case 1: 6 33 59 */