传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1166
网上的资料有树状数组入门讲解：点击打开链接（两个图很形象）
树状数组的核心思想就是二分，很巧妙的二分，是在二进制的基础上实现。可能需要理解一段时间，不郭参考资料很详细了。可以像最后的图那样，把二进制都写出来，更容易理解。可以简单理解为更新和求和时对二进制位有关系的操作（个人理解）
这个题题意就是最基本的RMQ吧，单点更新区间求和，上一个树状数组模板就好，可以根据这个第一步运用树状数组
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<vector> #include<queue> using namespace std; int c[100005],a[100005]; int n; int lowbit(int x){///清空高位1，计算2^k return x&(-x); } void modify(int x,int add){///更新 while(x<=n){///n为数组总长度 c[x]+=add; x+=lowbit(x); } } int sum(int x){///求和，从1到x的和 int ans=0; while(x>0){///大于0 ans+=c[x]; x-=lowbit(x); } return ans; } int get(int x,int y){ return sum(y)-sum(x-1); } int main(){ int i,j,T; int x,y; scanf("%d",&T); int k=0; while(T--){ k++; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]); modify(i,a[i]); } printf("Case %d:\n",k); char s[10]; while(scanf("%s",s)==1){ if(strcmp(s,"End")==0) break; scanf("%d %d",&x,&y); if(strcmp(s,"Query")==0){ printf("%d\n",get(x,y)); } if(strcmp(s,"Add")==0){ a[x]+=y;///更新后再对树状数组更新 modify(x,y); } if(strcmp(s,"Sub")==0){ a[x]-=y; modify(x,-y); } } } return 0; } 单点更新区间求和是树状数组的强项