ZROI-7-17

day 1 倍增 RMQ ST表 LCA

1. 算法介绍

倍增 RMQ

PS: 就是 ST 表

RMQ 问题

给定一个大小为 $n$ 的数组 $A$ ，有 $m$ 次询问，每一次给定两个数 $a, b$, 求

$min(or\ max)_{a \le k \le b}\{A_k\}$

1. 考虑暴力

ans = A[a];
for(int i = a + 1; i <= b; i++) ans = min(ans, A[i]);

复杂度 $\Theta(nq)$

2. 考虑倍增

设 f[i][j] 表示从 i 开始取 2^j 个数的最小值，如果 i 及其后面的数不足 2^j 个则全取，形式化地说，就是下标在$ [i, min(n,i+2^j-1)] $这个区间内的数的最小值。
转移：

$f[i][j] = min(f[i][j-1],\ f[i+2^{j-1}][j-1]),\ j>0\ and\ i+2^{j-1}<=n$

$= f[i][j-1],\ \ \ j>0\ and\ i+2^{j-1}>n$

$= a[i], j=0$

可以按照 j 从小到大的顺序递推出 f。

倍增LCA

1. lca的定义 $\cdots\cdots$

考虑维护 an[i][j] 表示 i 号节点的第 2^j 级祖先，如果没有则为 0。转移即：

an[i][j] = an[an[i][j-1]][j-1], j > 0
           = fa[i],           j = 0

这个可以通过树上 dfs 一遍求得。

考虑两个相同深度的点 x,y 的 lca 怎么求。(假定 x != y)

显然它们到 lca 的距离相同，假设距离为 d。

对于任意的 r>=d, 那么 x 的 r 级祖先和 y 的 r 级祖先相同，对于任意的 r<d, x 的 r 级祖先和 y 的 r 级祖先不同。

可以按照 k 从大往小的顺序，每次看两个点的第 2^k 级祖先是否相同，如果相同则什么也不做，如果不同则将两个点改成它们的第 2^k 级祖先。

这样做下去，直至 k = 0。求出的两个点一定是要求的 lca 的儿子。(为什么？)

当 x 和 y 深度不同的时候怎么办？

不妨假设 dep[x]>dep[y]，设 x 的 dep[x]-dep[y] 级祖先为 z。那么 lca(z,y)=lca(x,y)，dep[z]=dep[y], 于是求 lca(z,y) 即可。

怎么求 z？

考虑将 dep[x]-dep[y] 拆成 log 个 2 的幂跳。