思路：就是树状数组的模板题，利用的就是单点更新和区间求和是树状数组的强项时间复杂度为m*log(n)
没想到自己以前把这道题当线段树的单点更新刷了。
树状数组：
#include#include #include using namespace std;const int maxn = 5e4 + 10;int tree[maxn], n;void add(int k, int num){ while (k <= n) { tree[k] += num; k += k&-k; }}int sum(int k){ int sum = 0; while (k) { sum += tree[k]; k -= k&-k; } return sum;}int main(){ int t, x, y, k=0; scanf("%d", &t); while (t--) { memset(tree, 0, sizeof(tree)); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &x); add(i, x); } char num[20]; printf("Case %d:\n", ++k); while (scanf("%s", num), strcmp(num, "End") != 0) { scanf("%d%d", &x, &y); if (strcmp(num,"Add")==0){ add(x, y); } else if (strcmp(num,"Sub")==0){ add(x, -y); } else{ printf("%d\n", sum(y) - sum(x-1)); } } }}
线段树
#include#include #include using namespace std;#define MID(a,b) (a+((b-a)>>1))#define MAXN int(1e4)*5+5struct node{ int l, r; int sum; int mid(){ return MID(l, r); }};int num[MAXN], n;struct Tree{ node tree[MAXN << 2]; void build(int L, int R, int pos) { tree[pos].l = L; tree[pos].r = R; //表示区间 tree[pos].sum = 0; if (L == R){tree[pos].sum = num[R]; return; }//到了子叶 int mid = tree[pos].mid(); //二分 build(L, mid, pos<<1); build(mid + 1, R, pos << 1 | 1); tree[pos].sum = tree[pos << 1].sum + tree[pos << 1 | 1].sum; } //valu 表示加的值, ind 表示第几个军营。（在区域中的位置） void updata(int ind, int pos, int valu) { if (tree[pos].l == tree[pos].r) { tree[pos].sum += valu; return; //叶节点+valu } int mid = tree[pos].mid(); //二分查找单点位置？ if (ind <= mid) updata(ind, pos << 1, valu); else updata(ind, pos << 1 | 1, valu); tree[pos].sum = tree[pos << 1].sum + tree[pos << 1 | 1].sum; //递归，覆盖上一层的sum } //查询 int query(int L, int R, int pos)//从根节点查到符合的区间节点 { if (L <= tree[pos].l&&tree[pos].r <= R) return tree[pos].sum; int mid = tree[pos].mid(); int sum1 = 0, sum2 = 0; if (L <= mid) sum1 = query(L, R, pos << 1); if (R > mid) sum2 = query(L, R, pos << 1 | 1); return sum1 + sum2; }};Tree tree;int main(){ int x, y; int t, n,t_case=0; scanf("%d", &t); while (t--) { char ch[20]; scanf("%d", &n); printf("Case %d:\n", ++t_case); for (int i = 1; i <= n; i++) scanf("%d", &num[i]); tree.build(1, n, 1); while (scanf("%s", ch) != EOF) { if (strcmp(ch, "End") == 0) break; else if (strcmp(ch,"Add")==0) { scanf("%d%d", &x, &y); tree.updata(x, 1, y); } else if (strcmp(ch, "Sub") == 0) { scanf("%d%d", &x, &y); tree.updata(x, 1, -y); } else if (strcmp(ch, "Query") == 0) { scanf("%d%d", &x, &y); printf("%d\n", tree.query(x, y, 1)); } } } return 0;}