Binary Lifting

Published: March 18, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 快速幂技术
• 倍增技术
• 倍增结构

快速幂技术

快速幂技术是一种非常高效且简单的优化技术。对于环$U$上的某个元素$x$，我们要求$x^n$，我们可以用快速幂技术仅用$O(\log_2n)$次乘法运算即可高效完成这个过程。

快速幂的原理如下：

$$\left\{ \begin{array}{lclr} x^n&=&(x^{\frac{n}{2}})^2 &,2\mid n\\ x^n&=&(x^{\frac{n-1}{2}})^2\cdot x &,else \end{array} \right.$$

即根据$n$的奇偶性走两套逻辑。定义$T(n)$表示指数为$n$所需要执行的运算次数，可以发现$T(n)=T(n/2)+O(1)$，因此有$T(n)=O(\log_2n)$。

快速幂能适用于一切满足结合律的运算，不仅限于乘法运算。下面给出一些例题：

题目1：要求仅用加法以及位运算计算两个整数的乘积$a\cdot b$。

可以发现$a\cdot b=\sum_{i=1}^ba$，而加法也是满足结合律的，因此可以用快速幂来优化。

题目2：计算斐波那契数列的第$10^{18}$项的后四位数字。

由于斐波那契是线性递推数列，因此我们可以用矩阵来表示递推关系。而矩阵的乘法运算是满足结合律的。

题目3：有$n$个石头($n\leq 10^9$)，两个人进行比赛，每个人每次可以拿走$a_1,a_2,\ldots,a_m$块石头，这里$a_1,\ldots,a_m\leq 20$且一定包含$1$。拿走最后一块石头的人为输家。问在最优决策的情况下，哪一方一定会获胜。

可以用DP计算，但是$n$太大了。我们发现每个状态都仅有最多前面$20$个状态所完全决定，因此我们可以定义一个函数$f:Z_2^{20}\rightarrow Z_2^{20}$，暴力算出前20个状态，其向量形式记作$s$，而我们要计算的实际上是$f^{n-19}(s)$。由于函数的复合满足结合律，因此可以用快速幂加速。每次函数复合的时间复杂度为$O(2^{20})$，总的时间复杂度为$O(20+2^{20}\log_2n)$。

倍增技术

给定一个有向图$G=(V,E)$，每个结点只有唯一的出边，记$next(u)$表示$u$沿着唯一的出边移动一步后抵达的位置，记$link(u,i)$表示从$u$出发，通过少于$i$次的$next$转移能抵达的所有结点的集合。

在图上进行倍增实际上就是我们维护另外一个序列$jump(u,i)$，它表示$u$沿着出边移动$2^i$步所在的位置。很显然有$jump(u,0)=next(u)$，且$jump(u,i)=jump(jump(u,i-1),i-1)$。因此我们可以$O(V\log_2V)$求解出所有整个$jump$。

可以发现我们可以在做jump的时候同时进行二分，类似在线段树上进行二分。

并且如果仅仅为了二分的话，倍增实际上可以做到$O(n)$的预处理空间复杂度和处理时间复杂度的。详情可以参考这篇文章。

题目1：给定$n$个区间$s_1,\ldots,s_n$，如果两个区间独立，当且仅当它们没有交点。现在要求回答$q$个请求，每个请求给定$L,R$，要求仅考虑落在$L,R$中的区间，要求找到它们的最大独立集大小。

首先我们可以认为给定的区间没有包含关系（否则，较小的区间肯定更优，我们可以删除那些包含其它区间的区间）。

实际上对于每个请求，我们可以发现存在一个贪心算法，就是我们给定左边界$L$后，找到一个左边界大于$L$的区间，同时要求它的右边界最小。由于区间没有包含关系，因此等价于找到左边界最小（但是大于$L$）的区间$[l,r]$，之后我们把$L$更新为$r$。重复这个过程，直到找不到满足条件的区间为止。

之后考虑如何处理多个请求。

我们可以先让区间按照左边界进行排序，现在问题变成了仅考虑$s_l,s_{l+1},\ldots,s_r$，最大独立集大小。记$next(i)$表示$s_i$右边最小的下标$j$，满足$s_j$的左边界大于$s_i$的右边界。之后在上面建立倍增关系。那么问题就变成了从$s_l$出发最多可以移动多少步而不越界，这个可以在jump数组上进行二分解决。每个请求可以$O(\log_2n)$解决。

倍增结构

读这部分内容之前需要先读倍增技术部分。

倍增技术的强大是基于一个很简单的倍增结构。这个结构实际上还有额外的用处，我们可以将$jump(u,i)$视作一个结点，它覆盖了所有从$link(u,2^i)$上的结点，称$i$为这个结点的高度。

那么如果现在有这样的一些问题，我们需要处理若干个请求，每个请求要求修改路径$link(u,l)$上的所有结点。在所有请求完成后，要求输出所有结点的权值。

我们实际上可以发现$u,v$对应的区间可以截断为$O(\log_2n)$个倍增结构上的结点，我们只需要在这些结点上打上标记就可以了。并且考虑到标记只需要从高度较大的结点下推到高度较小的结点，因此在最后阶段我们可以从高到低处理结点。

当然这个问题平平无奇，LCT数据结构也可以做到$O(n\log_2n)$，但是倍增结构可以处理存在环的情况，而LCT就需要比较复杂的特殊处理。

现在再考虑一个问题，给定$n$个结点，之后有$q$个请求。每个请求给定两端等长区间$(a,b)$和$(c,d)$，表示对于所有$0\leq i\leq b-a$，结点$a+i$和$c+i$在同一个连通块中。接下来要求计算最多可能存在多少个连通块。

我们可以考虑把并查集的合并关系维护到我们的倍增结构上去，这样的话每次合并只涉及到$O(\log_2n)$个倍增结构上的顶点。类似的最后先处理高度较大的顶点下推合并关系即可。

再来考虑一个问题。现在有$n$个人，以及一颗大小为$m$的树。第$i$个人可以居住在$u_i$和$v_i$之间的路径上的任意一个顶点中，且一个顶点最多居住一个人。现在希望让尽可能多人居住在树上，问最多有多少人可以居住在树上。

可以发现每个结点只有一个父亲，因此我们把$next(u)$设置为$u$的父亲。之后我们建立网络流，将第$i$个人向路径$u_i$到$v_i$上的所有结点连一条边，借助倍增结构，我们可以只需要向$O(\log_2m)$个结点连边。这样我们得到了一个包含$O(m\log_2m+n)$个结点和$O((n+m)\log_2m)$条边的网络。之后求最大流即可。