本文共 2776 字,大约阅读时间需要 9 分钟。
单点更新,区间求和
#include#include #include using namespace std;const int MAXN = 50000+5;int n;int tree[MAXN<<2];int add[MAXN<<2];int a[MAXN<<2];char cmd[10];void build(int p, int l, int r) { if(l == r){ tree[p] = a[l]; return; } int m = (l+r)>>1; build(p<<1,l,m); build(p<<1|1,m+1,r); tree[p] = tree[p<<1]+tree[p<<1|1]; }void updateOne(int p, int l, int r, int ind, int x) { if(l == r){ tree[p] += x; return; } int m = (l+r)>>1; if(ind <= m) updateOne(p<<1,l,m,ind,x); else updateOne(p<<1|1,m+1,r,ind,x); tree[p] = tree[p<<1] + tree[p<<1|1]; } int query(int p, int l, int r, int tl, int tr) { if(l >= tl && r <= tr){ return tree[p]; } int m = (l+r)>>1; int ans = 0; if(tl <= m) ans += query(p<<1,l,m,tl,tr); if(tr > m) //这里不能写成else if 切记 ans += query(p<<1|1,m+1,r,tl,tr); return ans; }int main() { int t; // freopen("C:/Users/zhangwei/Desktop/input.txt","r",stdin); scanf("%d",&t); int kcase = 0; while(t--){ printf("Case %d:\n",++kcase); scanf("%d",&n); memset(tree,0,sizeof(tree)); memset(add,0,sizeof(add)); memset(a,0,sizeof(a)); for(int i = 1; i <= n; ++i){ scanf("%d",&a[i]); } build(1,1,n); int i,j; while(scanf("%s",cmd) == 1){ if(cmd[0] == 'E') break; scanf("%d%d",&i,&j); if(cmd[0] == 'A'){ updateOne(1,1,n,i,j); } else if (cmd[0] == 'S'){ updateOne(1,1,n,i,-j); } else if(cmd[0] == 'Q'){ printf("%d\n",query(1,1,n,i,j)); } } } return 0; }
转载地址:http://hrimi.baihongyu.com/