题意:
给定n个兵营的士兵初始值, 然后有最多40000个操作;
操作一共有两种, 一个是查询给定[a,b]区间兵营的士兵总和。
另一个是增加/减少指定兵营的士兵数目。
输出每次查询的值。
分析:
线段树单点更新模板
代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 50000 + 7; struct{ int l, r, sum; }tree[maxn*4];//起码要*4 int a[maxn]; int n; void build(int index, int l , int r){ tree[index].l = l, tree[index].r = r; if( l == r){ tree[index].sum = a[l];//递归建树,当l=r就是叶子节点没办法再分,直接赋值 return; } int mid = (l+r) / 2; build(index * 2, l, mid); build(index * 2 + 1, mid + 1 , r); tree[index].sum = tree[index * 2].sum + tree[index*2 + 1].sum;//不是叶子节点, 总和等于它儿子的总和 } void update(int index, int a, int val){ //修改总和的 if(tree[index].l == a && tree[index].r == a){ tree[index].sum += val;//找到该点,直接更改 return; } int mid = (tree[index].l + tree[index].r) / 2; if(a <= mid) update(index * 2, a , val); else update(index * 2 + 1, a, val); tree[index].sum += val;//路径上的点都要更改。 } int query(int index , int ql, int qr){ if(tree[index].l == ql && tree[index].r == qr){ return tree[index].sum; } int mid = (tree[index].l + tree[index].r) / 2; if(qr <= mid) //查询区间只在这个的左子树 return query(index * 2, ql, qr); if(ql > mid) //只在右子树 return query(index * 2 + 1, ql, qr); return query(index * 2, ql, mid) + query(index * 2 + 1, mid + 1, qr);//左右子树都有的话, 拆分查询区间 } int main(){ int T; scanf("%d", &T); int kase = 1; while(T--){ printf("Case %d: ", kase++); scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); } build(1,1,n); char cho[10]; while(scanf("%s",cho) && cho[0] != 'E'){ int x, y; scanf("%d %d", &x, &y); if(cho[0] == 'Q'){ printf("%d ", query(1,x,y)); } else if(cho[0] == 'A'){ update(1,x,y); } else update(1,x,-y); } } return 0; }