树状数组维护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$ 个数，用 $k$ 从 $log_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$ ，我们还会再给 $ans$ 加 $1$ 。于是 $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$ 就不会是原来那个数了）。