盈佳国际W11唯一指定手机版APP
  咨询电话:15146370985

盈佳国际W11唯一认证平台

倍增入门

倍增

线性倍增

预处理

(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=0;i<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(a,b); int t=0; if(dep[a]!=dep[b]){ while((1<<t)<=dep[a]) t++; t-=1; for(int i=t;i>=0;i--){ 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=t;i>=0;i--) if(f[a][i]!=f[b][i]) a=f[a][i], b=f[b][i]; return f[a][0];}