树状数组的模板题。 树状数组是一个查询和更新复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和。 关于树状数组的详解，可看下面的博客： https://blog.csdn.net/bestsort/article/details/80796531#区间修改-单点查询 核心是在lowbit函数上。 此题为树状数组的单点更新与区间求和问题。 代码如下：
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<iostream> #define mem(a,b) memset(a,0,(b+1)<<2) using namespace std; const int maxn=5e4+5; int c[maxn],a[maxn],n; int lowbit(int x) { return x&-x; } void update(int x,int k) //单点更新 { for(int i=x;i<=n;i+=lowbit(i)) c[i]+=k; } int inquire(int x) //查询[1,x]区间的和 { int sum=0; for(int i=x;i>0;i-=lowbit(i)) sum+=c[i]; return sum; } int main() { int T,kase=0; scanf("%d",&T); while(T--) { scanf("%d",&n); mem(c,n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); update(i,a[i]); } printf("Case %d:\n",++kase); char s[10]; int i,j; while(~scanf("%s",s)) { if(s[0]=='E') break; else if(s[0]=='A') { scanf("%d%d",&i,&j); a[i]+=j; update(i,j); } else if(s[0]=='S') { scanf("%d%d",&i,&j); a[i]-=j; update(i,-j); } else if(s[0]=='Q') { scanf("%d%d",&i,&j); printf("%d\n",inquire(j)-inquire(i)+a[i]); } } } return 0; }