ST表、树上倍增、LCA（模板合集）

st表

模板题：洛谷 P3865

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int f[100005][20];
int main()
{
    int n,m;
    int x,y;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i][0]);
    }
    for(int j=1;j<=21;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]);
        }
    }
    while(m--)
    {
        scanf("%d %d",&x,&y);
        int cc=log2(y-x+1);
        printf("%d\n",max(f[x][cc],f[y-(1<<cc)+1][cc]));
    }
    return 0;
}

树上倍增求LCA

参考文章

模板题：洛谷 P3379

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int head[1000005],dep[500005];
int f[500005][21],max0=20,cnt=1;
struct node
{
    int to,next,w;
}q[1000010];
void add(int x,int y)
{
    q[cnt].to=y;
    q[cnt].next=head[x];
    head[x]=cnt++;
}
void dfs(int u)
{
    for(int i=1;i<=max0;i++)
    {
        if(f[u][i-1])
        {f[u][i]=f[f[u][i-1]][i-1];} //在dfs(x)之前,x的父辈们的fa数组都已经计算完毕,所以可以用来计算x
        else
        {break;}//如果x已经没有第2^(i-1)个父亲了，那么也不会有更远的父亲，直接break
    }
    for(int i=head[u];i!=-1;i=q[i].next)
    {
        int v=q[i].to;
        if(v!=f[u][0]) //如果v不是x的父亲就是x的儿子
        {
            f[v][0]=u; //记录儿子的第一个父亲是x
            dep[v]=dep[u]+1; //处理深度
            dfs(v);
        }
    }
}
int LCA(int u,int v)
{
    if(dep[u]<dep[v]){swap(u,v);}//我们默认u的深度一开始大于v，那么如果u的深度小就交换u和v
    int delta=dep[u]-dep[v];//计算深度差
    for(int x=0;x<=max0;x++)//此循环用于提到相同的深度
    {
        if((1<<x)&delta)
        {u=f[u][x];}
    }
    if(u==v){return u;}
    for(int x=max0;x>=0;x--) ///注意！此处循环必须是从大到小!因为我们应该越提越“精确”
    {
        if(f[u][x]!=f[v][x])
        {
            u=f[u][x];
            v=f[v][x];
        }
    }
    return f[u][0];//此时u、v的第一个父亲就是LCA
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,s,x,y;
    scanf("%d %d %d",&n,&m,&s);
    for(int i=1;i<=n-1;i++)
    {scanf("%d %d",&x,&y);
    add(x,y);add(y,x);}//链式前向星存储这颗树
    dfs(s);//跑一遍dfs获得这颗树的信息，比如节点的父亲节点和深度
    while(m--)
    {
        scanf("%d %d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}

待更新~