倍增入门

约定不等于承诺〃 2021-11-30 00:58 212阅读 0赞

# 今天看不懂倍增代码，只好学了呀 #

首先

倍增，顾名思义就是一倍一倍的增加。举个例子你每次可以跳2的k次方步。现在你要跳到距离7步的地方。

跳8步 跳过了（不跳）

跳4步 没跳到（跳）

跳2步 没跳到 （跳）

跳1步 跳到 （停）

这里就只跳了3次 比普通的7次跳发优化了4次；

如果数据很大就是O(n) 和 O(logn)的区别了；

这里主要讲RMQ和LCA的2种简单算法  
RMQ:查找区间极值，而且还可以优化的

*  预处理的代码如下
    
    f数组的意思是以i为起点2的j次方长度的区间的极值是多少
    
    void ST(int n)///预处理  
    \{  
    for(int i=1;i<=n;i++)  
    f\[i\]\[0\]=a\[i\];///初始化以自己为起点2的0次方长的区间就是自己  
    for(int j=1;(1<<j)<=n;j++)///枚举区间长度  
    \{  
    for(int i=1;i+(1<<j)-1<=n;i++)///枚举起点  
    f\[i\]\[j\]=max(f\[i\]\[j-1\],f\[i+(1<<(j-1))\]\[j-1\]);  
    \}  
    \}  
    模拟一下：我们要得到f\[1\]\[1\]就可以通过f\[1\]\[0\]和f\[2\]\[0\]得到 f\[1\]\[2\]可以由f\[1\]\[1\]和f\[3\]\[1\]得到。由于我们是小区间得到大区间，所以比如求区间大小为8的时候，我们已经处理了所以4大小的区间了
    
    查询极值如下
    
    int RMQ(int l,int r)  
    \{  
    int k=trunc(log2( r-l+1 ));///向下取整  
    printf("k=%d\\n",k);  
      
    return max( f\[l\]\[k\], f\[r-(1<<k)+1\]\[k\] );  
    \}  
    代码处的k是找2个小一点的区间可以覆盖玩需要查询的区间，比如查找5长度的区间，我们就找2个长度为4的区间完全覆盖查询的区间。为什么能这样，举个例子1 2 4可以任意组合出1-7之内的所有数，正是这个性质才使得这个算法可以存在。
    
        1 #include<iostream>
         2 #include<cmath>
         3 #include<cstdio>
         4 using namespace std;
         5 int a[2000010];
         6 int f[2000010][21];
         7 int RMQ(int l,int r)
         8 {
         9     int k=trunc(log2(r-l+1));
        10     return min(f[l][k],f[r-(1<<k)+1][k]);
        11 }
        12 int main ()
        13 {
        14     int n,m;
        15     cin>>n>>m;
        16     for (int i=1;i<=n;i++)
        17         scanf("%d",&a[i]);
        18     for (int i=1;i<=n;i++)
        19        f[i][0]=a[i];
        20     for (int j=1;(1<<j)<=n;j++)
        21        for (int i=1;i+(1<<j)-1<=n;i++)
        22          f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        23     cout<<"0"<<endl;
        24     for (int i=2;i<=n;i++)
        25         printf("%d\n",RMQ(max(1,i-m),i-1));
        26  }
 *  LCA：最近公共祖先

LCA（最近公共祖先）也可以认为在树上找最短路，因为找到了最近公共祖先也就等于找到了最短路，维护一个dis\[\]数组表示所有节点到根节点的距离，u到v的最短距离就是dis\[u\]+dis\[v\]-2dis\[LCA(u,v)\]；

这个算法利用的是思想是找到u和v第一个不同祖先不同的位置，然后这个位置向上走一步就是最近公共的祖先。

但是u和v不在同一个深度肯定不行，所有需要dfs求去所有节点的深度

需要注意的是根据不同情况DFS是必须找到这个树的根节点，从根节点开始搜索

怎么找到根节点就开自己开标记数组处理啦！

void DFS(int u)  
\{  
for(int i=0;i<G\[u\].size();i++)  
\{  
int v=G\[u\]\[i\];  
if(vis\[v\]==0)  
\{  
vis\[v\]=1;///标记  
deep\[v\]=deep\[u\]+1;  
DFS(v);  
  
\}  
\}  
\}  
然后要做的就是倍增预处理每个节点上面2的k次方个祖先节点是什么

void ST(int n)///倍增预处理i 节点上面1<<j步的节点  
\{  
for(int j=1;(1<<j)<=n;j++)  
for(int i=1;i<=n;i++)  
f\[ i \] \[ j \] = f\[ f\[i\]\[j-1\] \] \[ j-1 \];  
\}  
需要注意的是输入边的时候就把f\[i\]\[0\]初始化好，f\[i\]\[0\]表示i节点上面2的0次方的祖先是什么，输入的时候很容易就初始化好了。

举个例子

f\[1\]\[0\]=0表示没有祖先，这个1节点就是根  
f\[2\]\[0\]=1表示2号节点祖先是1  
以此内推f\[4\]\[0\]=2 f\[5\]\[0\]=2 f\[3\]\[0\]=1  
处理f\[4\]\[1\]的时候就可以通过 f\[ f\[4\]\[0\]\] \[ 0 \]得到  
f\[4\]\[0\]=2 所以 f\[4\]\[1\]=f\[2\]\[0\]就意味着 i的上面2个节点可以通过i的上面1个节点的再跳1个节点得到 同理4个节点可以跳2次2个节点得到.

做完准备工作后就可以很高效的查询任意2个点的公共祖先了

int LCA(int u,int v)  
\{  
if(deep\[u\]<deep\[v\])///默认u的深度大一点简化后面的问题  
swap(u,v);  
int h=deep\[u\]-deep\[v\];///求出高度差  
for(int i=0;i<20;i++)///这个操作可以将u节点向上提升任意高度，觉得难懂就需要自己模拟一下过程  
\{  
if( h&(1<<i) )///二级制位上存在1就提升 1<<i步  
\{  
u=f\[u\]\[i\];  
\}  
\}  
if(u==v)///如果u==v表示 u就是v下面的分支节点  
return u;  
for(int i=19;i>=0;i--)///找到第一个不相同的节点  
\{  
if( f\[u\]\[i\]!=f\[v\]\[i\] )///还是利用了 1 2 4 可以任意组合出1-7所有的步数  
\{  
u=f\[u\]\[i\];  
v=f\[v\]\[i\];  
\}  
\}  
return f\[u\]\[0\];///第一个不相同的节点的上一个就是最近公共祖先  
\}

转载于:https://www.cnblogs.com/zjzjzj/p/11129134.html