考察： 线段树的建立 线段树的单点修改 线段树区间查询
#include<stdio.h> #include<iostream> #include<map> #include<algorithm> #include<cstring> #include<string.h> #include<string> #include<math.h> #include<vector> #include<map> using namespace std; typedef long long ll; #define MAXN 100005 #define INF 0x3f3f3f3f//将近int类型最大数的一半，而且乘2不会爆int #define MOD 1000000007 int tree[MAXN*2]; void build(int l, int r, int node) { //建立 if (l == r) { scanf("%d", &tree[node]); return; } int mid = (l + r)>>1; build(l, mid, node<<1); build(mid+1, r, node<<1|1); tree[node] = tree[node<<1] + tree[node<<1|1]; } void update(int p, int add, int l, int r, int node) { //add if (l == r) { tree[node] += add; //根结点+add return; } int m = (l + r) >> 1; if (p <= m) update(p, add, l, m, node << 1); else update(p, add, m+1, r, node << 1 | 1); tree[node] = tree[node << 1] + tree[node << 1 | 1]; } int query(int L, int R, int l, int r, int node) { //区间查询 if (L <= l && r <= R) return tree[node]; int m = (l + r) >> 1, ret=0; if (L <= m) ret += query(L, R, l, m, node << 1); if (R > m) ret += query(L, R, m+1, r, node << 1 | 1); 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); char sh[10]; while (scanf("%s", sh) && sh[0] != 'E'){ int a, b; scanf("%d %d", &a, &b); if (sh[0] == 'A') update(a, b, 1, n, 1); else if (sh[0] == 'S') update(a, -b, 1, n, 1); else printf("%d\n", query(a, b, 1, n, 1));; } } return 0; }