Peter算法小课堂—树状数组

2023-12-24 17:19:11

问题

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

拓展应用

偏序问题

例一:逆序对(洛谷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;
}

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

文章来源:https://blog.csdn.net/zhang040818/article/details/132780621
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。