本篇將簡要介紹倍增法。倍增法（英語：binary lifting），顧名思義就是翻倍。它能夠使線性的處理轉(zhuǎn)化為對數(shù)級的處理，大大地優(yōu)化時間復(fù)雜度。這個方法在很多算法中均有應(yīng)用，其中最常用的是 RMQ 問題和求 LCA（最近公共祖先）。

一、什么是倍增？

倍增，字面意思就是“成倍增長”。這是指我們在進行遞推時，如果狀態(tài)空間很大，通常的線性遞推無法滿足時間與空間復(fù)雜度的要求，那么我們可以通過成倍增長的方式，只遞推狀態(tài)空間中在 2 的整數(shù)次冪位置上的值作為代表。當(dāng)需要其他位置上的值時，我們通過“任意整數(shù)可以表示成若干個2的次冪項的和”這一性質(zhì)，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我們遞推的問題的狀態(tài)空間關(guān)于2的次冪具有可劃分行。

“倍增”與“二進制劃分”兩個思想相互結(jié)合，降低了求解很多問題的時間與空間復(fù)雜度。快速冪其實就是“倍增”與“二進制劃分”思想的一種體現(xiàn)。其他應(yīng)用還有，序列上的倍增問題，求解RMQ（區(qū)間最值）問題的ST算法，求解最近公共祖先（LCA）等。

二、基本用法

倍增主要用途是為了查找單調(diào)數(shù)據(jù)組中某一數(shù)值。

比如：在一個數(shù)組a {2,5,7,11,19} 中查找最大的小于12的數(shù)字。

（1）樸素做法：從第一個數(shù)開始，一個一個往后枚舉，查找。

（2）二分做法：每次將數(shù)列分割一半判斷，并且進一步查找子區(qū)間。

（3）倍增做法：設(shè)定一個增長長度 p 和已確定長度 l，現(xiàn)在要確定 a[l+p] 是否滿足條件，若滿足條件（比12?。?，則p成2倍增長；否則 p 縮小范圍（試著縮小范圍判斷條件）。

主要代碼：

l=0;
p=1;
while(p)//如果還能擴增范圍(l)就繼續(xù)
{
    if(a[l+p]<12)
    {
        l+=p;//增加已知范圍
        p<<=1//成倍增長，相當(dāng)于p*=2
    }
    else
    {
        p>>=1;//縮小范圍
    }
}
cout<<a[l];

倍增算法一般比較穩(wěn)定，時間 O(logn)。

三、ST算法

在RMQ問題（區(qū)間最值問題）中，著名的ST算法就是倍增的產(chǎn)物，給定一個長度為 N 的數(shù)列 A，ST算法能在O(N logN) 時間的預(yù)處理后，以 O(1) 的時間復(fù)雜度在線回答“數(shù)列 A 中下標(biāo)在 l~r 之間的數(shù)的最大值是多少”這樣的區(qū)間最值問題。

一個序列的子區(qū)間個數(shù)顯然有 O(N^2) 個，根據(jù)倍增思想，我們首先在這個規(guī)模為 O(N^2) 的狀態(tài)空間里選擇一些 2 的整數(shù)次冪的位置作為代表值。

設(shè) F[i,j] 表示數(shù)列 A中下標(biāo)在子區(qū)間 [i,i+2^j-1] 里的數(shù)的最大值，也就是從 i 開始的 2^j 個數(shù)的最大值。遞推邊界顯然是 F[i,0] = A[i]，即數(shù)列 A 在子區(qū)間 [i,i] 里的最大值。

在遞推時，我們把子區(qū)間的長度成倍增長，有公式 F[i,j] = max(F[i,j-1],F[i+2^(j-1),j-1])，即長度為 2^j 的子區(qū)間的最大值是左右兩半長度為 2^(j-1) 的子區(qū)間的最大值中較大的一個。

void ST——prework(){
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

當(dāng)詢問任意區(qū)間 [l,r] 的最值時，我們先計算出一個 k，滿足 2^k < r - l +1 ≤ 2^(k+1)，也就是使 2 的 k 次冪小于區(qū)間長度的前提下最大的 k。那么“從 l 開始的 2^k 個數(shù)”和“以 r 結(jié)尾的 2^k 個數(shù)”這兩段一定覆蓋了整個區(qū)間 [l,r]，這兩段的最大值分別是 F[l,r] 和 F[r-2^k+1,k]，兩者中較大的那個就是整個區(qū)間 [l,r] 的最值。因為求的是最大值，所以這兩段只要覆蓋區(qū)間 [l,r] 即可，即使有重疊也沒問題。

int ST_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

四、最近公共祖先（LCA）

給定一顆有根樹，若節(jié)點 z 既是節(jié)點 x 的祖先，也是節(jié)點 y 的祖先，則稱 z 是 x，y 的公共祖先。在 x，y 的所有共公共祖先中，深度最大的一個稱為 x，y 的最近公共祖先，記為 LCA(x,y)。

LCA(x,y) 是 x 到根的路徑與 y 到根的路徑的交匯點，它也是 x 與 y 之間的路徑上深度最小的節(jié)點。

這里著重介紹樹上倍增法求LCA。

樹上倍增法是一個很重要的算法。除了求 LCA 之外，它在很多問題中都有廣泛應(yīng)用。設(shè) F[x,k] 表示 x 的 2^k 輩祖先，即從 x 向根節(jié)點走 2^k 步到達的節(jié)點。特別地，若該節(jié)點不存在，則令 F[x,k] = 0. F[x,0] 就是 x 的父節(jié)點。除此之外，任意k∈[1,log n]，F(xiàn)[x,k]=F[F[x,k-1],k-1]。

這類似于一個動態(tài)規(guī)劃的過程，“階段”就是節(jié)點的深度。因此，我們可以對樹進行廣度優(yōu)先遍歷，按照層次順序，在節(jié)點入隊之前，計算它在F數(shù)組中相應(yīng)的值。

以上部分是預(yù)處理，時間復(fù)雜度為O(nlogn)，之后可以多次對不同的 x，y 計算 LCA，每次詢問的時間復(fù)雜度為 O(logn)。

基于F數(shù)組計算 LCA(x,y) 分為以下幾步：

設(shè) d[x] 表示 x 的深度。不妨設(shè) d[x]≥d[y]（否則交換 x，y）

用二進制拆分思想，把 x 向上調(diào)整到與 y 同一深度。具體來說，就是依次嘗試從 x 向上走      k = 2^logn,...,2^1,2^1步，檢查到達的節(jié)點是否比 y 深。在每次檢查中，若是，則令 x=F[x,k]

若此時 x=y，說明已經(jīng)找到了 LCA，LCA 就等于 y。

用二進制拆分思想，把 x，y 同時向上調(diào)整，并保持深度一致且二者不相會。具體來說，就是依次嘗試把 x，y 同時向上走 k=2^logn,...,2^1,2^0步，在每次嘗試中，若 F[x,k] ≠ F[y,k]（即仍未相會），則令 x = F[x,k]，y = F[y,k]。

此時 x，y 必定只差一步就相會了，它們的父節(jié)點 F[x,0] 就是 LCA。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int maxn=101000;
int n;
int m;
int s;
int tot;
int head[maxn];
int lg[maxn];
int depth[maxn];
int fa[maxn][32];
 
struct edge{
	int to;
	int from;
	int nxt;
}e[2*maxn];
 
void add(int x,int y){
	tot++;
	e[tot].to=y;
	e[tot].from=x;
	e[tot].nxt=head[x];
	head[x]=tot;
}
 
void dfs(int now,int fath){
	fa[now][0]=fath;
	depth[now]=depth[fath]+1;
	for(int i=1;i<=lg[depth[now]];i++) fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=head[now];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fath) continue;
		dfs(y,now);
	}
}
 
int lca(int x,int y){
	if(depth[x]<depth[y]) swap(x,y);
	while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];
	if(x==y) return x;
	for(int k=lg[depth[x]]-1;k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
 
int x,y;
 
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(s,0);
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
}