简介

倍增法，通过把线性处理转化为数级处理，从而优化时间复杂度。一般体现为距离一个节点 $2^{\N}$ 等形式。

应用

ST表

用于解决 RMQ 问题，可实现每次查询 $O(1)$ 的时间复杂度。

int n, m;
std::array<int, 100002> ln;
ln[1] = 0;
for(int i = 2; i <= n; ++i) 
  ln[i] = ln[i >> 1] + 1;
std::array<std::array<int, 20>, 100002> f;
for(int j = 1; j <= ln[n]; ++j) 
  for(int i = 1; i <= n - (1 << j) + 1; ++i) 
    f[i][j] = std::max(f[i][j-1], f[i + (1 << (j-1))][j-1]);
while(m--) {
  int li, ri;
  int len = ln[ri-li+1];
  std::max(f[li][len], f[ri-(1 << len)+1][len]);
}

树上倍增(一般用于LCA)

求出每个节点的数级祖先，每次查询时求最远非公共祖先的祖先。

int LCA(int x,int y) {
  if(dep[x] < dep[y]) swap(x, y);
  int d = dep[x] - dep[y];
  for(int k = 0; k <= J; ++k)
    if(d & (1<<k)) x = fa[k][x];
  if(x == y) return x;
  for(int k = J; k >= 0; --k)
    if(fa[k][x] != fa[k][y]) {
      x = fa[k][x];
      y = fa[k][y];
    }
  return fa[0][x];
}