首页 > 编程学习 > 树状数组

树状数组

发布时间:2022/8/25 17:45:47

树状数组是一种解决区间相关问题的数据结构,代码十分简洁,但复杂的问题处理不了。

问题引入

对于一个给定的数组a,可以进行单点修改以及区间求和。
如果只是要求区间求和的话,那么前缀和就可以解决,但是如果要修改某个位置的值,
那么前缀和数组的大部分数据都要修改,很费时间。
而树状数组可以完美的解决这个问题。

树状数组

用c表示树状数组,
c[i]=a[i-lowbit(i)+1]+...+a[i]
lowbit(i)=((x)&(-x))
就是说,树状数组里的数据是部分前缀和(前缀和的后半部分),其长度为lowbit(i)。
在i的二进制表示中,其末尾连续个0的个数为k,那么\(2^k=lowbit(i)\)

例如
7的二进制为111,k=0,那么c[7]=a[7]
8的二进制为1000,k=3,那么c[8]=a[1]+a[2]...+a[8]

在计算机中,-x为x的补码,换个说法,在二进制中,补码就是从右往左找到第一个不为0的数(其实就是1),
保持其不变,然后左边剩余数字全部取反,所以x&(-x)就表示x末尾连续个0的个数。

就不写这些设定是怎么来的了,我不会,下面会给出一些正确性证明

那么我们就可以通过lowbit(i)轻松获得从c[i]表示区间的长度。
现在考虑用c[i]来表示前缀和。
即如何用数组c表示a[1]+a[2]+...a[x]

int sum(int ind){
	int ans=0;
	for(int i=ind;i>0;i-=lowbit(i))ans+=c[i];
	return ans;
}

这个很好理解,只要将不同的c[i]拼起来就可以了。

然后是单点修改,假设我们修改了a[x],那么所有包含a[x]的c[i]都要修改,一直改到数组的上限。

void update(int ind,int k){
	while(ind<=n){
		c[ind]+=k;
		ind+=lowbit(ind);
	}
}

下面来简单证明一下为什么包含a[x]的点是c[x],c[x+lowbit(x)],c[c+lowbit(x)+lowbit(c+lowbit(x))],...

我们先从二进制的角度看下lowbit()
为减少码量,在这里我将二进制中最右边的1称为"关键1"。
x+lowbit(x)就是让关键1产生进位,那么得到结果的关键1肯定向左移动了
x-lowbit(x)将当前数字的关键1变为0,得到结果的关键1也左移了。
例如
100110 \(\to\) 101000 (+lowbit)
100110 \(\to\) 100100 (-lowbit)

首先,在c中包含a[x]的第一个数一定为c[x],现在令\(x+lowbit(x)=x_1\)
\(x_1\)的关键1一定在\(x\)的左边,并且\(x_1\)关键1的左半部分与\(x\)是相同的,因为进位到这里就停止了。
\(c[x]表示的范围a[x-lowbit(x)+1]...a[x]\)
\(c[x_1]表示的范围a[x_1-lowbit(x_1)+1]...a[x_1]\)
那么有\(x_1>x\)\(x_1-lowbit(x_1)\le x-lowbit(x)\)
那么\(x_1\)完全把\(x\)包住了,所以也一定包含a[x]

现在来看\(x与x_1\)之间会不会有其他数字也包含a[x]
\(x<x_2<x_1\)
可以发现\(x_2\)的关键1一定在\(x\)的右边,那么就有\(x_2-lowbit(x_2)\ge x\),就是说\(c[x]与c[x_2]\)不重叠。

所以要得到包含a[x]的c[i],一直往上加lowbit就行了。。

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号