个人觉得树状数组十分好用，虽然功能十分简单，但却可以用来优化其他题中的查询与修改...
数据结构就没学多少，就学好这个吧！
单点修改与区间查询：
#include<bits/stdc++.h> using namespace std; const int N=501000; int n,m,a[N],c[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline int lowbit(int x) {return x&(-x);} inline void add(int x,int k) { for(;x<=n;x+=lowbit(x)) c[x]+=k; } inline int ask(int x) { int ans=0; for(;x>0;x-=lowbit(x)) ans+=c[x]; return ans; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(register int i=1;i<=n;++i) a[i]=read(),add(i,a[i]); for(register int i=1;i<=m;++i) { int p=read(),x=read(),y=read(); if(p==1) add(x,y); else if(p==2) printf("%d\n",ask(y)-ask(x-1)); } return 0; }
区间修改与单点查询：
#include<bits/stdc++.h> using namespace std; const int N=501000; int n,m,a[N],c[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline int lowbit(int x){return x&(-x);} inline void add(int x,int k) { for(;x<=n;x+=lowbit(x)) c[x]+=k; } inline int ask(int x) { int ans=0; for(;x>0;x-=lowbit(x)) ans+=c[x]; return ans; } int main() { // freopen("1.in","r",stdin); n=read();m=read(); for(register int i=1;i<=n;++i) a[i]=read(),add(i,a[i]-a[i-1]); for(register int i=1;i<=m;++i) { int p=read(); if(p==1) { int x=read(),y=read(),k=read(); add(x,k);add(y+1,-k); } else if(p==2) { int x=read(); printf("%d\n",ask(x)); } } return 0; }
#include<bits/stdc++.h> #define ll long long using namespace std; const ll N=101000; ll n,m,sum1[N],sum2[N],a[N]; inline ll read() { ll x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline ll lowbit(ll x){return x&(-x);} inline void add(ll x,ll k) { int i=x; for(;x<=n;x+=lowbit(x)) sum1[x]+=k,sum2[x]+=(i-1)*k; } inline ll ask(ll x) { ll ans=0,i=x; for(;x>0;x-=lowbit(x)) ans+=i*sum1[x]-sum2[x]; return ans; } int main() { freopen("1.in","r",stdin); n=read();m=read(); for(register int i=1;i<=n;++i) a[i]=read(),add(i,a[i]-a[i-1]); for(register int i=1;i<=m;++i) { int p=read(); if(p==1) { ll x=read(),y=read(),k=read(); add(x,k);add(y+1,-k); } else if(p==2) { ll x=read(),y=read(); printf("%ld\n",ask(y)-ask(x-1)); } } return 0; }
好，这样就全齐了，总结一下，其中单点修改，单点查询，区间查询就是比较传统的树状数组..而区间修改则需要更改为差分，区间查询则更需要多开一个数组...
原文：https://www.cnblogs.com/gcfer/p/11609887.html