前言：

怎么標題改來改去的？

概念

因為每一個整數都可以轉換成對應的二進制，所以可以表示成 \(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)\)

4.并查集（tarjan）

首先遍歷所有的點，把他丟入并查集，在回溯的時候玩記錄代表元頂，就是 LCA！

時間復雜度：額，取決于并查集的時間復雜度。

void dfs(int u,int fa){
  for(auto v : ve[u]){
    if(v == fa) continue;
    dfs(v,u);
    fa[v] = u;
  }
  for(auto v : edges[u]){
    int id = v.second;
    int to = v.first;
    if(vis[to]){
      ans[id] = find(to);
    }
  }
  vis[u] = 1;
}

代碼（倍增）：

#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;
}