前言：
怎么标题改来改去的？
概念
因为每一个整数都可以转换成对应的二进制，所以可以表示成 \(a_0 \times 2^0 + a_1 \times 2 ^ 1 + a_2 \times 2 ^ 2 + a_{len} \times 2 ^ {len}\)。
因此，对于求跳 \(x\) 步后的状态，可以先预处理 \(2^{len}\) 的表，每次跳跃从一步一步往上跳进化成每次跳 \(2^{i}\) 步。
这就是倍增的概念。
用处
比如求 \(\operatorname{LCA}\)，就可以用倍增从 \(O(qn)\) 优化到 \(O(q \log _2n)\)。
接下来的 ST 表也是运用了倍增！
ST 表
ST 表（Sparse Table），是处理静态 RMQ 问题的一种高效算法（可重复贡献问题）。
对于无法进行相加减得到区间答案的问题，如 \(\max,\min\)，并且区间重叠对答案不受影响的（加或减就不是），可使用 ST 表来求解 RMQ。
令 \(dp_{i,j}\) 为以 \(i\) 为起点，往右 \(2^j\) 个单位的极值是多少。
那么就可以用 \(dp_{i,j-1}\) 和 \(dp_{i+(1<<j-1),j-1}\) 求极值。
单词询问时，就像扣了两锅盖，把两个锅盖求极值就好了！
优点：单次询问是 \(O(1)\) 的
缺点：无法在低时间复杂度修改 ST 表
所以，能用 ST 表就不用线段树（常数之王）！
例题：最近公共祖先（LCA）
方法 ( \(T\) 次询问)
1. 暴力法
记录深度，把深度较深的节点向上移动
时间复杂度：\(O(Tn)\)
2. 倍增
预处理每个节点向上 \(2^k\) 层的祖先
查询时通过二进制跳跃快速找到 \(\operatorname{LCA}\)
dp[i][j] = dp[dp[i][j-1]][j-1];
时间复杂度：\(O(T\log_2n)\)
3.dfs 序
对树进行 \(dfs\) 遍历，记录访问顺序和深度
记录每个节点首次出现的位置
用 \(ST\) 表来求出两个节点 dfs 序之间深度最小的节点
时间复杂度：\(O(n \log _2n + T)\)
代码（倍增）：
#include <bits/stdc++.h>using namespace std;
const int N = 5e5 + 7;
const int LOG_N = 21;
int f[N][LOG_N],dep[N];
vector<int>ve[N];
inline void dfs(int u,int fa){for(auto v : ve[u]){if(v == fa) continue;dep[v] = dep[u] + 1;f[v][0] = u;dfs(v,u);}return;
}
int get_lca(int x,int y){if(dep[x] < dep[y]) swap(x,y);int d = dep[x] - dep[y];for(int i = 0;d;i++,d >>= 1){if(d & 1){x = f[x][i];}}if(x != y){for(int i = 20;i >= 0;i--){if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}}x = f[x][0]; }return x;
}
int n,m,s;
int main(){scanf("%d%d%d",&n,&m,&s);for(int i = 1,x,y;i < n;i++){scanf("%d%d",&x,&y);ve[x].push_back(y);ve[y].push_back(x);}dep[s] = 1;dfs(s,s);for(int j = 1;j <= 20;j++){for(int i = 1;i <= n;i++){f[i][j] = f[f[i][j-1]][j-1];}}for(int u,v;m--;){scanf("%d%d",&u,&v);printf("%d\n",get_lca(u,v));}return 0;
}