很基础的线段树，本人做的第一个线段树题目，建树、插入、删除等功能会实现就可以了，另外不知道为什么用映射数组模拟一直WA。。。。ORZ
代码如下：
#include<iostream>using namespace std;const int maxsize = 50000;struct Stree{ int left, right; int cover;};Stree tree[3*maxsize];int sum;void Creat(int l, int r, int i){ tree[i].left = l; tree[i].right = r; tree[i].cover = 0; if (l == r)return ; int mid = (l + r)/2; Creat(l, mid, 2*i); Creat(mid+1, r, 2*i+1); }void Insert(int num, int i, int j){ int a = tree[num].left, b = tree[num].right; if (i >= a && i <= b){ tree[num].cover += j; } if (a == b)return ; if (i < a || i > b)return ; int mid = (a + b)/2; if (i <= mid)Insert(2*num, i, j); if (i > mid)Insert(2*num+1, i, j);}void counter(int num, int l, int r){ int a = tree[num].left, b = tree[num].right; int mid = (a + b)/2; if (l == a && r == b){ sum += tree[num].cover; return ; } else if (l > mid)counter(2*num+1, l, r); else if (r <= mid)counter(2*num, l, r); else { counter(2*num, l, mid); counter(2*num+1, mid+1, r); } }int main(){ int t; scanf("%d", &t); int ss = 0; while (t--){ int n; scanf("%d", &n); Creat(1, n, 1); for (int i = 1; i <= n; i ++){ int k; scanf("%d", &k); Insert(1, i, k); } printf("Case %d:/n",++ss); string s; while (cin >> s && s!="End"){ int loc, num; if (s == "Add"){ scanf("%d%d", &loc, &num); Insert(1, loc, num); } if (s == "Sub"){ scanf("%d%d", &loc, &num); Insert(1, loc, -num); } if (s == "Query"){ scanf("%d%d", &loc, &num); sum = 0; counter(1, loc, num); printf("%d/n",sum); } } } return 0; }
