ST&LCA

ST表

引言

给出一个长度为$n$的数组,再给出$m$个询问,每次询问任意区间$[l,r]$的最小值。

这是一个常见的RMQ问题。显然当n,m为$10^5$量级时,暴力$n^2$算法行不通。

当然这种可以区间合并的问题我们都可以用线段树来解决($nlogn$),而且线段树应用范围还会比ST倍增算法更广。

但是由于当m很大的时候线段树可能会被卡常(不会真的有出题人这么丧心病狂吧),同时引入LCA的倍增求法,还是来写下ST倍增算法吧。

正文

首先,要求一个任意区间$[l,r]$,如果我们知道两个区间$[l,k]$和$[k,r]$,同时保证这两个区间能完全覆盖$[l,r]$,那么这两个区间的min再min一下就可以了。

我们先预处理一下,用$dp[i][j]$表示区间起始点为$i$,长度为$2^j$的区间的最小值(倍增算法的核心)

显然$dp[i][0]$应初始化为$a[i]$

同时可以得到dp的递推公式 $dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])$

$dp[i][j-1]$表示前半部分,$dp[i+(1<<(j-1))][j-1])$表示后半部分。

那么怎么查询任意区间呢?我们不妨令$k=log2(r-l+1)$,显然$\frac{r-l+1}{2}<=2^k<r-l+1$

这样就回到一开始的问题可以实现$O1$查询了。

同理RMQ还可以用来查询区间gcd等区间合并会有重复但不影响结果的东西。

贴下模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void stinit(int n){
    for(int i=1;i<=n;i++) dp[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int query(int l,int r){
    int k=log2(r-l+1);
    int res=max(dp[l][k],dp[r-(1<<k)+1][k]);
    return res;
}

LCA

给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

lca.png

如果询问只有一次,很简单,我们只需要顺着两个点往上走,求出两条链,然后最早在两条链中均有出现的点就是最近公共祖先。比如说3,5的最近公共祖先。两条链为3->1->4, 5->1->4,所以3,5的lca为1。

但当询问次数一大,这种暴力方法显然不可取了。

所以我们可以考虑用上面的ST表来加速这种暴力方法。

比如说要求节点u,v的最近公共祖先

我们先dfs一遍求出u,v到根的距离$dis$,接下来把节点较深的那个移至和另一个节点dis相同的距离。

一步一步移太慢了,由于任意一个数都可以由二进制来表示,我们每次走$2^i$的步,$i$同时减小就可以。($i$的初值可以设为$log2(dis[u])$或一个比较大的常数,比如20。

注意移到相同层次时会有一个特殊情况,即v是u的祖先,这种情况直接返回v即可。

一般情况下,移动同一层次后,若u往上走$2^i$步与v往上走$2^i$步不为同一个点,则将它们同时往上走$2^i$步,这样移动后就能保证father[u]=father[v](这里相当于用二进制来表示dis[u]到dis[lca(u,v)]的距离)

那么怎么用代码来实现移动呢?

可以发现我们移动的步数都是$2^i$步,因此可以用st表来预处理出$p[i][j]$表示编号为$i$的节点向上$2^j$单位的祖先节点。

贴个模板:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
#define ll long long
#define debug(x) cout<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5e5+10;
vector<int>g[maxn];
int dis[maxn],p[maxn][25],par[maxn];
void dfs(int u,int fa){
    par[u]=fa;
    for(int i=0;i<g[u].size();i++)
    {
        if(g[u][i]==fa) continue;
        dis[g[u][i]]=dis[u]+1;
        dfs(g[u][i],u);
    }
}
void lca(int n,int s){
    memset(dis,0,sizeof(dis));
    dis[s]=1;dfs(s,0);
    memset(p,-1,sizeof(p));
    for(int i=1;i<=n;i++) p[i][0]=par[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++){
            if(p[i][j-1]!=-1)
            p[i][j]=p[p[i][j-1]][j-1];
        }
}
int query(int u,int v){
    if(dis[u]<dis[v])  swap(u,v);//深度深的设为u
    //int log=log2(dis[u]);
    for(int i=20;i>=0;i--)
        if(dis[p[u][i]]>=dis[v]) u=p[u][i];//移至同一层
    if(u==v) return u;
    for(int i=20;i>=0;i--){
        if(p[u][i]!=-1&&p[u][i]!=p[v][i]){
            u=p[u][i];v=p[v][i];
        }
    }
    return par[u];
}
int main()
{
   int n,m,s;
   cin>>n>>m>>s;
   for(int i=1;i<n;i++){
       int u,v;
       cin>>u>>v;
       g[u].push_back(v);
       g[v].push_back(u);
   }
   lca(n,s);
   while(m--)
   {
       int u,v;
       cin>>u>>v;
      cout<<query(u,v)<<endl;
   }
   return 0;
}