浅谈如何用单栈模拟队列

· · 算法·理论

考虑这样一个问题:维护一个栈,支持加入新元素,删除最早加入的元素,强制在线。

我们先考虑能不能对这个算法的时间复杂度有一个合理的预期。

首先注意到这个问题的离线版本可以直接用线段树分治解决,所以我们可以猜测同样有均摊 O(\log n) 的在线算法。

然后我们说明不存在均摊低于 \Theta(\log n) 次 pop 的做法。我们考虑这样一个弱化的问题:初始时栈内有 n 个 0,做 n 次操作,每次删除一个 0,加入一个 1。设解决这个问题所需的最小 pop 次数为 T(n)。由于所有的 0 都被删掉了,必然有一次操作把整个栈的元素全部 pop 了出来(否则最下面的 0 不可能出栈),设这次操作为第 k 次。那么我们删除前 k-1 个元素至少用 T(k-1) 次 pop(因为无视对前 k-1 次没删掉的元素的 pop/push 就能规约到规模 k-1 的问题),第 k 次操作用 n 次 pop,后 n-k 次操作至少用 T(n-k) 次 pop(无视掉对新加入的 k 个元素的 pop/push)。于是 T(n) \geq \min_{1 \leq k \leq n} \{T(k-1)+T(n-k)+n\}。注意到这个式子就像是求一个二叉树的子树大小和,而这等于所有节点的深度和(根的深度为 1)。至少有 \lceil n/2 \rceil 个点深度 \geq\lfloor\log_2 n\rfloor,于是 T(n)=\Omega(n \log n)。

所以我们可以预期一个均摊 \Theta(\log n) 的做法。

我们先考虑给出一个弱化版的 \Theta(n\log n) 做法。很明显可以把大小为 n 的完全二叉树建出来,每个节点以中序遍历的顺序对应最开始从栈顶到栈底的 0。中序遍历整个二叉树,对于每个点 x,遍历完 x 的左子树后,把栈顶的 x 的子树大小个元素 pop 出来,按原顺序把所有 1 塞到下面,所有 0 放在栈顶,然后 pop 0 并 push 1,继续中序遍历右子树。根据之前的分析,这样我们会 pop \Theta(n \log n) 次。push 次数和 pop 是同阶的,所以总时间复杂度 \Theta(n \log n)。

当然实际上可能不止加入了 n 个 1。我们只需要稍作修改,把「pop 出栈顶的子树大小个元素」改成「不断 pop 栈顶直到 pop 出右子树大小 +1 个 0」就可以了。现在我们说明这种做法仍能保证时间复杂度的正确性。假设我们加入了 m 个 1,之前的论证仍能说明 0 只被 pop/push 了 \Theta(n \log n) 次,那 1 呢?观察到如果我们在中序遍历 x 时 pop 了某个 1,那么它在 x 的子树遍历完成之前都不会再动了。所以每个 1 最多被 pop 树高次,总次数是 \Theta(m \log n) 的。总时间复杂度为 \Theta(m \log n)。

然后我们发现其实不需要显式地在二叉树上中序遍历,因为唯一用到这棵树的信息的地方是「不断 pop 栈顶直到 pop 出右子树大小 +1 个 0」,而右子树大小 +1 其实就是当前剩下的 0 的数量的 \text{lowbit}。所以,我们只需要在加入 1 时正常 push,删除 0 时如果栈顶是 0 就直接删(想想为什么),如果不是 0 就把 \text{lowbit}(cnt_0) 个 0 提到栈顶就好了。

现在我们考察一般的问题。我们把一部分元素标成 old(对应 0),剩下的标成 new(对应 1)。加入时把元素标成 new 放在栈顶。在 old 删完后,我们把整个栈的元素全部 pop 再反过来 push 让栈逆序,并把所有元素标成 old。由于每个元素的标记至多只会变化一次,所以这个重构均摊是 O(1) 的。综上所述,我们得到了一个单次操作均摊时间复杂度 \Theta(\log n) 的算法。

实际应用的话,比如给你 m 条无向边,对于所有 i=1,2,\cdots,m,求最大的 r_i 使得编号 i,i+1,\cdots,r_i 的边构成的子图无环。用上述方法结合双指针 + 可撤销并查集即可。总之可撤销数据结构都能套(

さらってほしいの - ヒトリエ