周报

树状数组

2020年3月26日

简单来说，树状数组是一种可以解决区间求和和前缀最值问题的数据结构。其大概结构如下图：

所以有：$c[1]=a[1]$

$ c[2]=a[1]+a[2] $

$ c[3]=a[3] $

$ c[4]=a[1]+a[2]+a[3]+a[4]。$

$……$

然后这些关系可以通过lowbit获取。lowbit(x)表示的是$2^k$,k是从最低位到高位的0的个数。比如说$(4)_10=(100)_2$,所以$lowbit(4)=2$。然后我们要从儿子x到达父亲y的话，可以让$x+=lowbit(x)$。

然后下面说树状数组的操作：

树状数组的修改

插入的话就是通过儿子节点不断的往上传，每次到达一个节点然后更新，然后移到这个节点的父亲上。代码如下：

void update(int x,int dat){
	while (x<=tot){
		c[x]+=dat;
		x+=lowbit(x);
	}
}

树状数组的查询

查询的话是求1~n树状数组中所有值的和。由于c[i]中存的是一部分的区间之和，所以我们只要对这部分节点求和就行了。

比如说上图中对1~7求和，易知$ans=c[7]+c[6]+c[4]$，然后找到这些点只需要让$x-=lowbit(x)$就行了。代码如下：

int getNum(int x){
	int ret=0;
	while (x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret; 
}

然后知道两种操作之后我们就可以搞一些高端操作了，比方说：

单点修改和区间求和

这个直接用上面两种操作就行了。

区间修改和单点查询

这个可以用差分数组来维护，不过上面查询查出来的值是单点的值。

树状数组求逆序对

比如说给出一列数，要求逆序对。应该先对数进行离散化（获取数间大小关系的一种操作），然后按排名插入树状数组的对应位置上。每次插入之后统计一下已经插入的比这个数大的数的个数，最后统计的结果就是逆序对的个数

区间修改和区间查询

这个的话依然是考虑用差分数组来维护，不过区间查询的话要另外维护一个数组

因为$c[i]=a[i]-a[i-1]$

所以$\sum_{i=1}^n a[i]\quad$

$=a[1]+a[2]+…+a[n]$

$=c[1]+c[1]+c[2]+…+a[1]+a[2]+…+a[n]$

$=n*c[1]+(n-1)*c[2]+…+a[n]$

$=\sum_{i=1}^n (n-i+1)*(c[i])\quad$

$=\sum_{i=1}^n n*c[i]\quad-\sum_{i=1}^n (i-1)*c[i]\quad$

所以额外维护一个$(i-1)*c[i]$的数组就行了。求和就直接套上面的公式

代码：

int update(int x,int dat){
	while (x<=m){
		c[x]+=dat;
		d[x]+=dat*(x-1);
		x+=lowbit(x);
	}
}

二维树状数组

这个就和一维的树状数组差不多，把操作稍微改一下就行了。代码：

int getNum(int x,int y){
	int ret=0;
	for (int i=x;i>0;i-=lowbit(i))
		for (int j=y;j>0;j-=lowbit(j))
			ret+=c[i][j];
	return ret;
}

void update(int x,int y,int dat){
	for (int i=x;i<=n;i+=lowbit(i))
		for (int j=y;j<=n;j+=lowbit(j))
			c[i][j]+=dat;
}

例题

HDU1556

POJ2299

POJ3067

POJ3321 <-这个题还挺有意思的

POJ2155

Views: 61

发表评论