倍增法
倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 LCA（最近公共祖先） 。
ST(Sparse Table)表，中文名稀疏表，是一种数据结构。
ST表常用于解决可重复贡献问题。其实就是倍增法的cache版本。
什么是可重复贡献问题？
常见的可重复贡献问题有：区间最值、区间按位和、区间按位或、区间GCD等。二而像区间和这样的问题就不是可重复贡献问题。
题目特点是求的k可以很大，但都没有关系，因为都会二进制变成log(n)的时间复杂度。
所以solution的时间复杂度一般是o(nlogn)
模板 树上倍增算法（以及最近公共祖先）
class TreeAncestor:
def __init__(self, n: int, parent: List[int]):
m = n.bit_length() - 1
pa = [[p] + [-1] * m for p in parent]
for i in range(m):
for x in range(n):
if (p := pa[x][i]) != -1:
pa[x][i + 1] = pa[p][i]
self.pa = pa
def getKthAncestor(self, node: int, k: int) -> int:
for i in range(k.bit_length()):
if (k >> i) & 1: # k 的二进制从低到高第 i 位是 1
node = self.pa[node][i]
if node < 0: break
return node
# 另一种写法，不断去掉 k 的最低位的 1
def getKthAncestor2(self, node: int, k: int) -> int:
while k and node != -1: # 也可以写成 ~node
lb = k & -k
node = self.pa[node][lb.bit_length() - 1]
k ^= lb
return node
模板2 O(nlog)初始化，然后O(logn)查询
- 求第k大祖先。
- 求lca.
'''
root节点为0
'''
class TreeAncestor:
def __init__(self, edges: List[List[int]]):
n = len(edges) + 1
m = n.bit_length()
g = [[] for _ in range(n)]
for x, y in edges: # 节点编号从 0 开始
g[x].append(y)
g[y].append(x)
depth = [0] * n
pa = [[-1] * m for _ in range(n)]
def dfs(x: int, fa: int) -> None:
pa[x][0] = fa
for y in g[x]:
if y != fa:
depth[y] = depth[x] + 1
dfs(y, x)
dfs(0, -1)
for i in range(m - 1):
for x in range(n):
if (p := pa[x][i]) != -1:
pa[x][i + 1] = pa[p][i]
self.depth = depth
self.pa = pa
def get_kth_ancestor(self, node: int, k: int) -> int:
for i in range(k.bit_length()):
if (k >> i) & 1: # k 二进制从低到高第 i 位是 1
node = self.pa[node][i]
return node
# 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
def get_lca(self, x: int, y: int) -> int:
if self.depth[x] > self.depth[y]:
x, y = y, x
# 使 y 和 x 在同一深度
y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])
if y == x:
return x
for i in range(len(self.pa[x]) - 1, -1, -1):
px, py = self.pa[x][i], self.pa[y][i]
if px != py:
x, y = px, py # 同时上跳 2**i 步
return self.pa[x][0]
题目
使用ST表处理问题
需要对区间最值ST表略作修改即可。
比如区间按位与，则只需修改以下代码：
f[i][j]=f[i][j-1]&f[i+(1<<(j-1))][j-1];//倍增的处理
ans=f[l][lg]&f[r-(1<<lg)+1][lg];//区间重叠运算
再比如区间GCD：
f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);//倍增的处理
ans=gcd(f[l][lg],f[r-(1<<lg)+1][lg]);//区间重叠运算
值得一提的是，处理区间GCD时，ST表与线段树的时间复杂度基本相近，但前者却显然要好写得多。
ST表的缺点在于其只能处理可重复贡献问题，以及其不支持区间修改罢了。