树状数组维护01序列

(鉴于没几个人访问这个博客,这是一篇写给自己复习的超低质量文章。)

看这样一个例子:假如桌上依次排列高度为1,2,3,…,n的圆柱体,给定m个操作,对于每次操作,取出第i个圆柱体,并且输出取出的这个圆柱体的高度。(取出第i个圆柱之后,第i+1个圆柱就变成了新序列中的第i个圆柱,第i+2个圆柱就变成了新序列中的第i+1个圆柱,以此类推)

解决

如何高效地解决这个问题呢?考虑到树状数组能高效动态维护前缀和的特点,我们可以用01串表示每个高度的圆柱体是否仍然存在。如果这个01串的前k项的前缀和为i,那么说明当前剩余的第i个圆柱体的高度为k。

但是,这样做并不能提高查找效率,反而使问题更复杂。因为如果我们暴力枚举第1~n项的前缀和,还不如直接从第1项向后累加。(O(nlog_2n)O(n)还差)

由于这个01串的前缀和一定是单调不下降的(新增一项之后,前缀和要么不变,要么加1),我们就可以用二分的方式,来二分前缀和等于i的位置。这样做的效率是O( log_2^2 n)

取出第i个圆柱(假设是k)之后,调用add(k,-1)即可。

查找代码如下:

int query(int x)
//查找当前剩余圆柱的第x项的高度
//需要将存在情况的01串保存到树状数组中
//ask即为01串求前缀和的函数
{
	int l=1,r=n;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(ask(mid)<x) l=mid+1; else r=mid;
	}
	return l;
}

可不可以更优呢?

让我们回忆一下树状数组是如何保存数据的:

int ask(int x)
{
	int ans=0;
	for(;x;x-=x&-x) ans+=c[x];
	return ans;
}

void add(int x,int y)
{
	for(;x<=n;x+=x&-x) c[x]+=y;
}

假如我们把这个树状数组命名为c,那么c[i]表示的是第i-lowbit _(i)+1到第i个元素的和。举个例子,c[10]=c[1010_2]保存的是第1001_2(即1010_2-lowbit(1010_2)+1)到第1010_2个数的和。

想到什么了么?倍增啊。

我们无需调用树状数组的ask()函数,只需要使用它的c[]数组。

首先初始化两个参数ans=sum=0

假设要求第i个数,用klog_2^n枚举到0,如果ans+2^k \le n (1)并且sum+c[ ans+2^k ] < i (2),就让sum加上c[ ans+2^k ]ans加上2^k
答案就是ans

这个算法的复杂度是O(log n)

为什么这么做是正确的?

这个序列是单调的,那么:

只要有一个k满足(1)&(2),那么第i个数的位置一定大于或者等于ans+2^k,所以我们把ans加上2^k。假如某些元素被删除了,那么这样的算法可以让我们向后移动,略过被删除的元素。

只要有一个k不满足这个条件(即sum+c[ans+2^k] \ge i),那么最后的结果一定小于 ans+2^k ,所以我们不加。又由于最后的结果一定可以被二进制拆分,所以这样算一定可以得到最后的结果。

推广

我们可以把这个算法推广到解决动态求解一个数列的第i项的值的问题。

写法有三种。前两种前面已经介绍了,分别是二分、通过在数列中的大小序号倍增(给出从1到i的i个数中,i的大小排名)。

还可以通过利用在数列中前面比它小(或大。这里以小为例)的数的个数倍增。 只有一点写法的区别。上一种倍增的条件2是 sum+c[ ans+2^k ] < i ,这一种的条件2是 sum+c[ ans+2^k ] \le i。两种答案都是ans+1。 实质上都差不多,把读入的数据加一减一就可以在这两种写法之间转换。

为什么上一种的倍增条件是 sum+c[ ans+2^k ] < i而不是 sum+c[ ans+2^k ] \le i ?假如有一个由1~n组成的数列a:

a[]:3 2 1 4 5

从第一项到这一项中,它的大小排位从小到大分别是:(即 将a[1]到a[i]从小到大排序,a[i]在排序后的数列中的下标)

b[]:1 1 1 4 5 

首先,我们初始化还没被选择的数的序列:11111(也就是每个数都可以选)。我们从最后一位推导。已知第5个数是数列中第5大的。满足ask(ans)=b[5]最大ans就是5

然后我们删掉5。01序列变为11110。

接着,我们求解第4个数。已知它是剩下的序列中第b[4]=4大的,那么我们寻找满足ask(ans)=b[4]最大k。这个时候,如果倍增的条件是 sum+c[ ans+2^k ] \le i ,那么在进行到k=4这一步时(此时sum=4),由于ask(4+1)=ask(4)=4,我们还会再给ans1。于是ans变为了5。但是很显然,这是错误的。

所以,我们需要将倍增条件改为 sum+c[ ans+2^k ] < i 。这个时候,ans会停留在满足ask(ans)=b[i]前一个数,并且滤过已经被删除的数。再加上1就可以得到我们需要的。

再举个例子,假如当前的01序列为1100001。我们要求第3大的数。

根据算法,我们要求ask(ans)<3最大ans

我们初始化ans=0,从k=2开始枚举(这里有7个数,\left\lfloor log_2^7\right\rfloor = 2)。可以发现,ask(ans+2^2=4)=2满足条件。于是令ans=ans+2^2=4,继续枚举k。当k=1时,仍然满足条件。所以ans=ans+2^1=6。这时k=0,而ans=ans+2^0=7的时候不再满足条件了。所以ans不变。枚举结束。这个时候,ans+1=7就是我们要求的数:7就是在剩下的3个数中第3大的。我们发现,使用这样的算法,可以把已被删去的数滤过,只要输入无误,算法结束后ans+1一定是还未被选的数(否则得到的ans就不会是原来那个数了)。

单独说出来是因为我发现《算法竞赛入门指南》中作者搞错了这点……

留下评论

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