优点：修改和查询树状数组的前缀和复杂度为O（logn）

注意点：树状数组对下标有要求，必须从1开始（1-base）

1.求数组前缀和

将原数组数组放入树状数组直接求sum即可

2.求数组某个元素的值

将原数组的差分数组放入树状数组，求sum

3.求逆序对

知识点：离散化

目的：节约内存，让下表更清晰，去重节约时间复杂度

实现代码

sort(t+1,t+n+1); cnt=unique(t+1,t+n+1)-t-1;

将离散化后的数组按顺序插入树状数组，求前缀和n-前缀和a[i].

模板：

#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl "\n" #define pb push_back #define dbg(x) std::cout<<#x<<":"<<x<<" " typedef long long ll; typedef pair<int,int> PII; const int N=500005; ll n,m; ll a[N]; ll lowbit(ll x) { return (x&(-x)); } void update(ll x,ll v){ while(x<=n){ a[x]+=v; x+=lowbit(x); } } ll sum(ll x){ ll res=0; while(x>0){ res+=a[x]; x-=lowbit(x); } return res; } void solve() { cin>>n>>m; ll w=n; ll tp; while(w--){ cin>>tp; update(n-w,tp); } ll a1,a2,a3; while(m--){ cin>>a1>>a2>>a3; if(a1==1){ update(a2,a3); } if(a1==2){ if(a2>1) cout<<sum(a3)-sum(a2-1)<<endl; else cout<<sum(a3)<<endl; } } } int main() { IOS int T=1;//cin>>T; while(T--) solve(); return 0; }

#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl "\n" #define pb push_back #define dbg(x) std::cout<<#x<<":"<<x<<" " typedef long long ll; typedef pair<int,int> PII; const int N=500005; int n,m; int a[N],b[N]; int lowbit(int x) { return (x&(-x)); } void update(int x,ll v){ while(x<=n){ a[x]+=v; x+=lowbit(x); } } ll sum(int x){ ll res=0; while(x>0){ res+=a[x]; x-=lowbit(x); } return res; } void solve() { cin>>n>>m; int w=n; ll tp; for(int i=1;i<=n;i++){ cin>>b[i]; update(i,b[i]-b[i-1]); } ll a1,a2,a3,a4; while(m--){ cin>>a1; if(a1==1){ cin>>a2>>a3>>a4; update(a2,a4); update(a3+1,-a4); } if(a1==2){ cin>>a2; cout<<sum(a2)<<endl; } } } int main() { IOS int T=1;//cin>>T; while(T--) solve(); return 0; }

例题：

题都不难，放了几个典型的

洛谷——逆序对

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+5; int n,cnt; ll a[N],b[N],t[N],ans; int lowbit(int x){ return x&(-x); } void update(int x){ while(x<=n){ a[x]++; x+=lowbit(x); } } ll sum(int x){ ll res=0; while(x>0){ res+=a[x]; x-=lowbit(x); } return res; } void solve() { cin>>n; for(int i=1;i<=n;i++){ cin>>b[i]; t[i]=b[i]; } sort(t+1,t+n+1); cnt=unique(t+1,t+n+1)-t-1; for(int i=1;i<=n;i++){ //按原顺序插入 b[i]=lower_bound(t+1,t+cnt+1,b[i])-t;//更新离散化后的序号 update(b[i]); //比当前元素大的=当前元素个数-小于等于它的元素个数 ans+=sum(n)-sum(b[i]); } printf("%lld\n",ans); } int main() { solve(); return 0; }

数星星

可以不用逆序对

#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl "\n" #define pb push_back #define dbg(x) std::cout<<#x<<":"<<x<<" " typedef long long ll; typedef pair<int,int> PII; const int N=32005; struct z{ int x,y; }; int n,m,MAX=0; int a[N],ans[N]; z p[N]; int lowbit(int x) { return (x&(-x)); } void update(int x,int v){ while(x<=N){ a[x]+=v; x+=lowbit(x); } } ll sum(int x){ ll res=0; while(x>0){ res+=a[x]; x-=lowbit(x); } return res; } void solve() { scanf("%d",&n); int x,y; for(int i=1;i<=n;i++){ scanf("%d %d",&p[i].x,&p[i].y); } for(int i=1;i<=n;i++){ update(p[i].x+1,1); int v=sum(p[i].x+1); ans[v-1]++; } for(int i=0;i<n;i++){ cout<<ans[i]<<endl; } } int main() { int T=1;//cin>>T; while(T--) solve(); return 0; }

逆序对写法和上个题基本一样按顺序求x的逆序对就好了，不写了

其实这个题有别的做法

我把update里的加改成了异或

#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false),cin.tie(0); #define endl "\n" #define pb push_back #define dbg(x) std::cout<<#x<<":"<<x<<" " typedef long long ll; typedef pair<int,int> PII; const int N=5000005; int n,m; int a[N],b[N]; int lowbit(int x) { return (x&(-x)); } void update(int x,int v){ while(x<=n){ a[x]^=v; x+=lowbit(x); } } ll sum(int x){ ll res=0; while(x>0){ res^=a[x]; x-=lowbit(x); } return res; } void solve() { cin>>n>>m; ll a1,a2,a3; while(m--){ scanf("%lld",&a1); if(a1==1){ scanf("%lld %lld",&a2,&a3); update(a2,1); update(a3+1,1); } if(a1==2){ scanf("%lld",&a2); cout<<sum(a2)<<endl; } } } int main() { int T=1;//cin>>T; while(T--) solve(); return 0; }