倍增入门

发布日期:2019-04-28

倍增

线性倍增

预处理

(f[i][j])表示从(i)开始的长度为(2^{j})的区间(即区间([i i+2^{j}-1])

递推公式(j在外层递增):

(f[i][j]=max{f[i][j-1] f[i+2^{j-1}][j-1]})

即将区间([l r])分为两个区间合并

查询

分为两段,第一段为区间([l k]),第二段为区间([r-k+1 r]),其中(k)为满足(2^{k}le r-l+1)的所有数中最大的那个数

(f[i][j]=max{f[i][k] f[j-2^{k}+1][j]})

树上倍增(求解LCA)

预处理

首先结合dfs预处理出(f[i][j])(f[i][j])表示节点(i)向上跳(2^{j})层的节点

递推公式:

(f[i][j]=f[f[i][j-1]][j-1])

即节点(i)分两次向上跳,每次跳(2^{j-1})层跳到的节点就是节点(i)向上跳(2^{j})层的节点((2^{j-1}imes 2=2^{j})

void dfs(int x int fa){ dep[x]=dep[fa]+1 f[x][0]=fa for(int j=1(1<<j)<=dep[x]j++) f[x][j]=f[f[x][j-1]][j-1] for(int i=0i<mp[x].size()i++) if(mp[x][i]!=fa) dfs(mp[x][i] x)}

同时也可以顺便预处理出(log^{n}_{2})的所有值以优化常数

查询

首先使两个查询节点跳至同一高度后(因为它们的最近公共祖先不可能低于这两点,跳跃方法同下),当前层记为(x),然后从(log^{x}_{2})到0枚举(递减能保证可以完全分解成二进制)(j),如果上跳(2^{j})层后不重合,那么就继续跳,重合则不跳,使两点层数一直逼近最近公共祖先,最后跳完(2^{0})层后,两点必定会停在最近公共祖先的下一层,所以最后直接取当前层(i)(f[i][0])就好了。

其中,每次取得k的while((1<<t)<=dep[a])循环可以如前文提到的那样先打表出(log^{n}_{2})的所有值以优化常数

int lca(int a int b){ if(dep[a]<dep[b]) swap(ab) int t=0 if(dep[a]!=dep[b]){ while((1<<t)<=dep[a]) t++ t-=1 for(int i=ti>=0i--){ if(dep[a]-(1<<i)>=dep[b]) a=f[a][i] } } if(a==b) return a t=0 while((1<<t)<=dep[a]) t++ t-=1 for(int i=ti>=0i--) if(f[a][i]!=f[b][i]) a=f[a][i] b=f[b][i] return f[a][0]}