Loading...

神奇的离线最值求法——倍增

check评论:2 条 remove_red_eye浏览量:798 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-08-19

标题说是倍增求离线最值,其实倍增也可以求和啊qwq

倍增是一种考虑每次将范围扩大或缩小一倍进而快速求出区间某些信息的思想,可以将$O(n)$的繁琐计算缩减至$O(logn)$

  • 倍增经典算法:ST表

在做RMQ问题时,我们经常用ST表(又称稀疏表)来实现

举个例子:

给定一个长度为n的数列,m次询问,每次一个区间[l,r]表示求区间[l,r]最小值

这种题看到的第一想法,或许是线段树,而线段树常数较大,所以这里用ST表来实现

首先通过倍增的定义,我们设$f(i,j)$代表从第$i$个数往后$2^j$个数内的最小值(包含第$i$个数),则查询区间$[l,r]$只需要求出$min(f[l][lg2[r-l+1]],f[r-(1<<lg2[r-l+1])+1][lg2[r-l+1]]$即可,即在$O(1)$内获得答案,而我们需要做哪些预处理呢?

  • $lg2$预处理

由于$math.h$里的$log2$函数运行速度感人,所以我们可以通过预处理一遍来获得答案,很容易可以得到递推式
$$lg2[i]=lg2[i>>1]+1\quad (i>=2)$$边界条件$lg2[1]=0$

即可在$O(n)$内预处理所有的$lg2$从而减少时间复杂度

  • $ST$表预处理

我们由倍增的思想来看,每一次将当前区间翻倍

而我们有的边界条件是$a[i][0]=num[i]$(管一个数就只有自己)

那如果我们求区间$[l,l+1]$呐?是不是就是$a[l][1]=min(a[l][0],a[l+1][0])$

再跳一倍$[l,l+3]$,就是$a[l][2]=min(a[l][1],a[l+2][1])$

......

所以可以得到区间$[l,l+2^k-1]$中,就是$a[l][k]=min(a[l][k-1],a[l+2^{k-1}][k-1])$

那么就可以得到递推公式:
$a[i][j]=min(a[i][j-1],a[i+(1<<(j-1))][j-1])$

那么问题是不是就可以比较容易地完成呐?

我们以洛谷P1816 忠诚为例

和上面的例子一模一样,所以我们可以直接用上面你的递推公式,得到预处理$ST$代码为:

for(int j=1;j<=lg2[n];j++)//最多往后跳pow(2,lg2[n])格
    {
        for(int i=1;i<=n+1-(1<<j);i++)//只要跳不超过范围
        {
            a[i][j]=min(a[i][j-1],a[i+(1<<(j-1))][j-1]);//上面得到的递推式
        }
    } 

那么我们就已经处理完$ST$表了!查询就变得很简单

int u=lg2[y-x+1];//区间内最多跳多少格
printf("%d ",min(a[x][u],a[y-(1<<u)+1][u]));//两边合并得到答案

这道题就愉快的结束了!

那么,如果用倍增来做一个平面上的问题呐?例子如下

给定一个n*n的矩阵,m次询问,每次查询矩阵(x1,y1)-(x2,y1)-(x2,y2)-(x1,y2)中所有数的最大公约数

我会二维分块/线段树!

其实不用,一看到静态区间求值就很容易能想到倍增,而$gcd$也是可以预处理之后$O(1)$得到答案的,因为$gcd$和$min$都满足部分重合答案不变的一个规律,而求和则不行,所以求和需要其他的方法。

还是和上面一个一样,我们知道边界条件即
$$f[i][j][0][0]=a[i][j]$$
可以得到和上面一样的公式$f[i][j][0][k]=gcd(f[i][j][0][k-1],f[i][j+(1<<(k-1))][0][k-1]$
纵向也类似,就可以得到预处理代码为:

for(int pi=0;pi<=P;pi++)
{
    for(int pj=0;pj<=P;pj++) 
    {
        if(pi==0&&pj==0) 
        {
            continue;
        }
        for(int i=1;1+(1<<pi)-1<=n;i++)
        {
            for(int j=1;j+(1<<pj)-1<=m;j++) 
            {
                if(pi==0) 
                {
                    st[i][j][pi][pj]=gcd(st[i][j][pi][pj-1],st[i][j+(1<<(pj-1))][pi][pj-1]);
                } 
                else 
                {
                    st[i][j][pi][pj]=gcd(st[i][j][pi-1][pj],st[i+(1<<(pi-1))][j][pi-1][pj]);
                }
            }
        }
    }
}      

查询也类似,可以在$O(1)$内得到答案

int dx=x2-x1+1;
int dy=y2-y1+1;
int px=logb[dx],py=logb[dy];
int ans1,ans2;
ans1=gcd(st[x1][y1][px][py],st[x2-(1<<px)+1][y1][px][py]);
ans2=gcd(st[x1][y2-(1<<py)+1][px][py],st[x2-(1<<px)+1][y2-(1<<py)+1][px][py]);
return gcd(ans1,ans2);
  • 倍增如何求和?

如果你还是按照上面的思路,即区间$[l,r]$的和为$f[l][lg2[r-l+1]]+f[r-(1<<lg2[r-l+1])+1][lg2[r-l+1]]$就错了,因为这样有很大的可能导致中间被重复计算

我们设这个区间为$[2,8]$,其长度为$7$

转变为二进制看看呐?$7_{(10)}=111_{(2)}$

那是不是意味着我们从$2$分别跳$2^0$,$2^1$,$2^2$步即可?即将长度转为二进制后找出每个$1$所在的位置再跳即可,我们可以用$lowbit(x)$来快速获得每个1对应的数,即该方法复杂度上界为$O(logn)$,下界为$O(1)$,还是非常快的了

找出第几位需要跳(二进制下是1)

int k=1;
while(a)
{
    if(a&1)
    {
        printf("%d\n",lg2[k]);
        k<<=1;
        a>>=1;
        continue;
    }
    k<<=1;    
    a>>=(int)lg2[lowbit(a)];
}

这样是不是就非常简单了呐?

  • 树上倍增

一般我们在求$LCA$时,都会采用树链剖分树上倍增的方法来实现

我们也是提前预处理出所有点往上跳$2^i$个点的位置,则边界条件为$$f[i][0]=fa[i]$$

$fa[i]$我们可以通过一遍dfs来获得

我们继续看公式,$f[i][1]=fa[fa[i]]$,$fa[i]$又等于$f[i][0]$,则$f[i][1]=f[f[i][0]][0]$

$f[i][2]=f[f[i][1]][1]$

$f[i][3]=f[f[i][2]][2]$

......

类似的,我们可以得到公式$f[i][j]=f[f[i][j-1]][j-1]$

就可以很容易的得到每个点向上跳$2^j$个点的位置啦

int dfs(int r,int u)
{ 
    d[u]=d[r]+1;//深度处理,保证往上跳不会越界
    f[u][0]=r;//f[i][0]=fa[i]
    for(int i=1;(1<<i)<=d[u];i++)//可以跳的范围之内
    {
        f[u][i]=f[f[u][i-1]][i-1];//预处理
    }
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=r)
        {
            dfs(v,u);//继续搜索
        }
    }
} 

那么,我们又如何查询$LCA$呐?

我们先将比较低的点跳到和高的点同一深度,然后同时往上跳。因为一个十进制数对应唯一的一个二进制数,所以我们枚举可以跳的方案,如果跳出了边界或者已经跳到了$LCA$的祖宗上,就不跳这一次,如此下去,最后跳完的结点的$fa$就是$LCA$,具体见代码

int lca(int a,int b)
{
    if(d[a]>d[b])//设置b为较深的店
    {
        swap(a,b);
    }
    for(int i=20;i>=0;i--)
    {
        if(d[a]<=d[b]-(1<<i))
        {
            b=f[b][i];//将a,b跳到同一深度
        }
    }
    if(a==b)//找到了
    {
        return a;
    }
    for(int i=20;i>=0;i--)
    {
        if(f[a][i]==f[b][i])
        //如果两个向上跳pow(2,i)个是一样的
        //即可以跳到LCA的祖先或者出界
        {
            continue;//就不跳了QAQ
        }
        b=f[b][i];
        a=f[a][i];
    }
    return f[a][0];
}

这样,就可以用可爱的倍增的方式找到$LCA$

其实,如果只是单纯的向上跳找结点,也可以用倍增。

例题:$P3379$[模板]最近公共祖先
$P3942$将军令(可以用倍增优化贪心)

由于博主非常菜,就先将这么多吧qwq

已有 2 条评论

正在回复给  
去登陆?

   点击刷新验证码

    M_sea
    2018 - 08 - 22 12 : 10

    树链剖分好啊

    然而我并不会

      可爱的诗和远方qwq
      2018 - 08 - 22 19 : 06

      Fake

标签云

文章留名