这里丢一篇很好的blogs
https://www.cnblogs.com/hsd-/p/6139376.html
其实树状数组的是实现是根据二进制的
主要的函数有这三个
int lowbit(int x) { return x&(-x); }
这个是返回原数上去除末尾一个1的数
such as
t=6（0110）-t=-6=(1001+1)=(1010)t&(-t)=(0010)=2 得到这个有什么用呢，继续看
int add(int i,int x) { while (i<=n) { c[i]+=x; i+=lowbit(i); } }
这个呢是树状数组实现单点修改
1 int sum(int i) 2 { 3 int res=0; 4 while (i>=1) 5 { 6 res+=c[i]; 7 i-=lowbit(i); 8 } 9 return res; 10 }
这个是实现区间求和查询跟上面的是一样的意识
树状数组求逆序对
#include<iostream> #include<algorithm> using namespace std; struct sb { int z,num; }t[1001]; int c[1001],n; bool cmp(sb a,sb b) { return a.z<b.z?true:false; } int lowbit(int x) { return x&(-x); } int add(int i,int x) { while (i<=n) { c[i]+=x; i+=lowbit(i); } } int sum(int i) { int res=0; while (i>=1) { res+=c[i]; i-=lowbit(i); } return res; } int main () { cin>>n; for (int i=1;i<=n;i++) { cin>>t[i].z; t[i].num=i; } sort(t+1,t+1+n,cmp); int ans=0; for (int i=1;i<=n;i++) { add(t[i].num,1); ans+=i-sum(t[i].num); } cout<<ans; }
原文：https://www.cnblogs.com/zjzjzj/p/10778816.html