在学习完了线段树后，听说树状数组能写的题，线段树都能做，所以一直没有详细的学习树状数组；直到碰到了一道卡线段树的题目，因为线段树运用了很多递归，所以常数比较大，容易被卡；现在总结一下树状数组；
学习树状数组前一定要把lowbit这个东西弄懂，建议百度；
1、树状数组个人认为就是前缀和演变而来的； 2、 单点更新：当你要更新某个点的值时，你要从下面到上面依次更新过去； 区间查询和单点查询：树状数组没有区间查询这个东西，都可以说是单点查询，就跟差不多前缀和，当你求区间[l.r]的和时，只要sum( r)-sum(l-1)就行；并且要从上到下依次相加，跟前缀和差不多； 3、 区间更新：这里的区间更新，就跟差分数组非常相似了，当你要求区间[l，r]都加上a时，差分数组是l点加上a，r+1这个点减去a；树状数组跟这一样；也可以说是单点更新；
模板： 1.单点更新+区间查询；求和操作；
#include<bits/stdc++.h> #define LL long long #define pa pair<int,int> #define lson k<<1 #define rson k<<1|1 //ios::sync_with_stdio(false); using namespace std; const int N=500100; const int M=200100; const LL mod=2e9+7; int n,m,tr[N]; int lowbit(int k){ return k & (-k); } void add(int p,int q){//p点加上q，单点修改 while(p<=n){ tr[p]+=q; p+=lowbit(p); } } int sum(int p){//单点查询，就是求前缀和 int s=0; while(p!=0){ s+=tr[p]; p-=lowbit(p); } return s; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++){ int x; cin>>x; add(i,x); } for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; if(a==1) add(b,c); else cout<<sum(c)-sum(b-1)<<endl; } return 0; }2.区间更新+单点查询；求和操作
#include<bits/stdc++.h> #define LL long long #define pa pair<int,int> #define lson k<<1 #define rson k<<1|1 //ios::sync_with_stdio(false); using namespace std; const int N=500100; const int M=200100; const LL mod=2e9+7; int n,m,tr[N]; int lowbit(int k){ return k & (-k); } void add(int p,int q){//p点加上q，单点修改 while(p<=n){ tr[p]+=q; p+=lowbit(p); } } int sum(int p){//单点查询，就是求前缀和 int s=0; while(p!=0){ s+=tr[p]; p-=lowbit(p); } return s; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; int last=0; for(int i=1;i<=n;i++){ int x; cin>>x; add(i,x-last);//差分 last=x; } for(int i=1;i<=m;i++){ int a,b,c,d; cin>>a; if(a==1){ cin>>b>>c>>d; add(b,d); add(c+1,-d);//差分的体现 } else{ cin>>b; cout<<sum(b)<<endl; } } return 0; }