Peter算法小课堂—树状数组

问题

我们从一个很常见的问题开始：高效率的查询和维护前缀和。何为前缀和，给定长度为n的数列A={a1,a2,a3......an},其中sum(x)=a1+a2+a3+......ax。如果A数列静态不变，那代码忒好写。但是，今天研究的就是：如果序列是动态变化的，即改变其中一个元素ak的值，那它后面的前缀和都会改变，那么复杂度为O(n)。但是Chloe觉得复杂度太高，想要调整到O()。因此引入传说中的“树状数组 and 线段树”

解决方案

定义一个树状数组tree[]，tree[]的值就是树下直连的子节点的和，例如8个点,tree[1]=a1,tree[2]=tree[1]+a2,tree[3]=a3,tree[4]=tree[3]+tree[2]+a4...利用树状数组可以高效的完成前面说的问题。

神奇的lowbit(x)

lowbit(x)=x&(-x),它的作用是找到x的二进制数的最后一个1

树状数组的编码

#define lowbit(x) (x&(-x))
#define N 1000
int tree[N];
void update(int x,int d){   //单点修改 
	while(x<N){
		tree[x]+=d;
		x+=lowbit(x);
	}
}
int sum(int x){ //查询前缀和 
	int ans=0;
	while(x>0){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}

简不简单？复杂度：O()

拓展应用

偏序问题

例一：逆序对（洛谷P1908）

方法：离散化，树状数组

代码

//lowbit(x),update(),sum()的代码前面已经给出
const int N=5000000;
int tree[N],r[N],n;
struct point{
	int num,val;
}a[N];
bool cmp(point x,point y){
	if(x.val==y.val) return x.num<y.num;
	return x.val<y.val;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].val;
		a[i].num=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) r[a[i].num]=i;
	long long ans=0;
	for(int i=1;i<=n;i++){
		update(rank[i],1);
		ans+=i-sum(rank[i]);
	}
	cout<<ans;
	return 0;
}

望大佬一圈三连哦φ(゜▽゜*)?