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 <iostream>
#include <algorithm>using namespace std;const int N = 1e5 + 10;
int n;
int a[N];struct Tree {int left, right;int sum;
}t[4*N];// 更新idx处的sum 
inline void pushup(int idx) { t[idx].sum = t[idx << 1].sum + t[idx << 1 | 1].sum;
}// 建树 
void build(int pos, int left, int right) {t[pos].left = left, t[pos].right = right;if (left == right) {t[pos].sum = a[left];return;}int mid = left + right >> 1;build(pos << 1, left, mid);build(pos << 1 | 1, mid + 1, right);pushup(pos);
}// index处的值加value 
void change(int pos, int index, int value) {if (t[pos].left == t[pos].right) {t[pos].sum += value;return;}int mid = t[pos].left + t[pos].right >> 1;if (index <= mid) {change(pos << 1, index, value);} else {change(pos << 1 | 1, index, value);}pushup(pos);
}// [left, right]区间内元素和 
int query(int pos, int left, int right) {if (t[pos].left >= left && t[pos].right <= right) {return t[pos].sum;}int mid = t[pos].left + t[pos].right >> 1;int tmp = 0;if (left <= mid) {tmp = query(pos << 1, left, right);}if (right > mid) {tmp += query(pos << 1 | 1, left, right);}return tmp;
}int main() {int t = 0;cin >> t;for (int k = 1; k <= t; k ++) {scanf("%d", &n);for (int i = 1; i <= n; i ++) {scanf("%d", &a[i]);}build(1, 1, n);string s;printf("Case %d:\n", k);while(true) {cin >> s;if (s == "End") {break;}int a, b;cin >> a >> b;if (s == "Query") {int r = query(1, a, b);printf("%d\n", r);} else if (s == "Add") {change(1, a, b);} else {change(1, a, -b);}}}return 0;
}