ACM

树状数组从入门到精通(

树状数组(Binary Indexed Tree)是一个查询和修改复杂度都为log(n)的数据结构。

百度百科

在算法竞赛中,我们经常遇到这样一种问题:对一段数据进行修改或查询,但是单次修改或查询为O(n)的算法却不能满足题目数据的要求。

思考这样一个问题:给定一个长度为n的序列,现在有q次查询,每次查询给出两个数x与y,要求你输出区间[x,y]内元素值之和。

不难想到,我们可以预先算出这段序列的前缀和,记录为s数组,每次查询输出s[x]-s[y-1]。这样时间复杂度就从O(nq)降低到O(n+q)了。

那么修改一下这个问题: 给定一个长度为n的序列,现在有q次操作,每次操作或是查询:给出两个数x与y,要求你输出区间[x,y]内元素值之和;或是修改:给出两个数m与x,要求你将序列里第m个元素的值修改为x。

那么在这种情况下修改的时间复杂度就变为了O(n),使得整体时间复杂度又变为O(nq)。

这样一来似乎问题变得复杂起来。如果是普通数组,那么单点修改时间复杂度是O(1),而区间查询时间复杂度是O(n);而如果是前缀数组,那么单点修改时间复杂度是O(n),而区间查询时间复杂度是O(1)……

于是一个集合了普通数组和前缀数组的优势的数据结构:树状数组出现了,树状数组利用二进制,让每一个c[i]表示了原数组中区间(i-lowbit[i],i]的元素值之和。从而使得单点修改与区间查询得时间复杂度都变为O(logn)。

其中,lowbit(x)是x的二进制表达式中最低位的1所对应的值,如6的二进制表达为110,最低位1代表了二进制的10,也就是2,因此lowbit(6)=2。

int lowbit(int x){
	return x&(-x);
}

树状数组是如何利用lowbit实现log级的查询的呢?

考虑一个数x的二进制表示中有k个1,那么定义s[1]=x,s[i]=s[i-1]-lowbit(s[i-1])。那么有数列中前x项和=c[s[1]]+c[s[2]]+c[s[3]]+……+c[s[k]]。仔细观察这个式子即可发现c[s[i]]和c[s[i-1]]所代表的两区间紧密相邻,那么将全部c[s[i]]相加所代表的区间恰为(0,x]。同时k不大于logx,所以单次查询时间复杂度为O(logn)。

int Query(int m){
	int sum=0;
	for (int i=m;i;i-=lowbit(i)) sum+=c[i];
	return sum;
}

树状数组是如何利用lowbit实现log级的修改的呢?

考虑一个数下标为m,可能序列长度为n。那么定义s[1]=m,s[i]=s[i-1]+lowbit(s[i-1])(s[i]<=n)。则有且仅有这些c[s[i]]覆盖该位置。那么我们修改该位置的元素时,将这些c[s[i]]均修改一遍即可。同时i最大为logn,所以单次修改时间复杂度为O(logn)。

void add(int m,int x){
	for (int i=m;i<=n;i+=lowbit(i)) c[i]+=x;
}

那么树状数组的三大主要函数都写完了,看一道例题:HDU1541

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define N 15001
int c[N],ans[N],n;
int lowbit(int x){
	return x&(-x);
}
int Query(int m){
	int sum=0;
	for (int i=m;i;i-=lowbit(i)) sum+=c[i];
	return sum;
}
void add(int m,int x){
	for (int i=m;i<N;i+=lowbit(i)) c[i]+=x;
}
int main(){
	while (~scanf("%d",&n)){
		memset(ans,0,sizeof(ans));
		memset(c,0,sizeof(c));
		for (int i=1,a,b;i<=n;i++){
			scanf("%d%d",&a,&b);
			add(a+1,1);
			ans[Query(a+1)]++;
		}
		for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
	}
    return 0;
}

树状数组并不仅仅只有维护区间和的应用,他同样可以实现维护区间最值的应用。

发表评论

电子邮件地址不会被公开。 必填项已用*标注