HDU1166

Lily特别喜欢养花，但是由于她的花特别多，所以照料这些花就变得不太容易。她把她的花依次排成一行，每盆花都有一个美观值。如果Lily把某盆花照料的好的话，这盆花的美观值就会上升，如果照料的不好的话，这盆花的美观值就会下降。有时，Lily想知道某段连续的花的美观值之和是多少，但是，Lily的算术不是很好，你能快速地告诉她结果吗?

Input

第一行一个整数T，表示有T组测试数据。
每组测试数据的第一行为一个正整数N (N<=50000)，表示Lily有N盆花。
接下来有N个正整数，第i个正整数ai (1<=ai<=50) 表示第i盆花的初始美观值。
接下来每行有一条命令，命令有4种形式：
（1）Add i j, i和j为正整数，表示第i盆花被照料的好，美观值增加j (j<=30)
（2）Sub i j, i和j为正整数，表示第i盆花被照料的不好，美观值减少j (j<=30)
（3）Query i j, i和j为正整数，i<=j，表示询问第i盆花到第j盆花的美观值之和
（4）End，表示结束，这条命令在每组数据最后出现
每组数据的命令不超过40000条

Output

对于第i组数据，首先输出"Case i:"和回车。
对于每个"Query i j"命令，输出第i盆花到第j盆花的美观值之和。

思路：就是线段树模板题，单点更新和区间求值

#include<cstdio>
#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l, mid, rt<<1
#define rson mid + 1, r, rt<<1|1
const int maxn = 5e4 + 10;
int tree[maxn << 2];void push_up(int rt)
{tree[rt] = tree[rt << 1] + tree[rt << 1|1];
}
void build(int l, int r, int rt)
{if(l == r){scanf("%d", &tree[rt]);return;}int mid = (l + r) >> 1;build(lson);build(rson);push_up(rt);
}
void update(int pos, int val, int l, int r, int rt)
{if(l == r){tree[rt] += val;return;}int mid = (l + r) >> 1;if(pos <= mid)update(pos, val, lson);elseupdate(pos, val, rson);push_up(rt);
}
int query(int L, int R, int l, int r, int rt)
{int ans = 0;if(L <= l && r <= R)return tree[rt];int mid = (l + r) >> 1;if(L <= mid)ans += query(L, R, lson);if(R > mid)ans += query(L, R, rson);return ans;
}int main()
{int t, t1 = 1;scanf("%d", &t);while(t--){printf("Case %d:\n", t1++);int n;scanf("%d", &n);build(1, n, 1);char s[6];while(cin >> s){if(s[0] == 'A'){int i, j;scanf("%d%d", &i, &j);update(i, j, 1, n, 1);}else if(s[0] == 'S'){int i, j;scanf("%d%d", &i, &j);update(i, -j, 1, n, 1);}else if(s[0] == 'Q'){int i, j;scanf("%d%d", &i, &j);printf("%d\n", query(i, j, 1, n, 1));}else if(s[0] == 'E')break;}}return 0;
}