倍增（LCA与ST表）附详细讲解博客路劲以及洛谷模板题

前置知识 -- 倍增

倍增算法，顾名思义，就是不断地翻倍。

虽然是一种基础算法，但它能够使得线性的处理转化为对数级的处理，大大地优化时间复杂度，在很多算法中都有应用，其中最常见的就是ST表以及LCA（树上最近公共祖先）了。

学习博客：算法学习笔记(12): ST表 - 知乎 (zhihu.com)

for(int x=1;x<=n;x++) to[x][0]=(x+k)%n+1,carrot[x][0]=num[x];
for(int i=1;i<=64;i++)
    for(int x=1;x<=n;x++)
    {
        to[x][i]=to[to[x][i-1]][i-1];
        carrot[x][i]=carrot[x][i-1]+carrot[to[x][i-1]][i-1];
    }
int p=0,now=1,ans=0;
while(m)
{//若m的二进制第p-1位为1，则答案加上去
    if(m&(1<<p)) ans+=carrot[now][p],now=to[now][p];
    m^=(1<<p);//第p-1位清空
    p++;
}

LCA 树上最近公共祖先

学习博客：算法详解之最近公共祖先(LCA) - hulean - 博客园 (cnblogs.com)

代码模板

// https://www.luogu.com.cn/problem/P3379
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct zzz {
    int t, nex;
}e[500010 << 1]; int head[500010], tot;
void add(int x, int y) {
    e[++tot].t = y;
    e[tot].nex = head[x];
    head[x] = tot;
}
int depth[500001], fa[500001][22], lg[500001];
void dfs(int now, int fath) {
    fa[now][0] = fath; depth[now] = depth[fath] + 1;
    for(int i = 1; i <= lg[depth[now]]; ++i)
        fa[now][i] = fa[fa[now][i-1]][i-1];
    for(int i = head[now]; i; i = e[i].nex)
        if(e[i].t != fath) dfs(e[i].t, now);
}
int LCA(int x, int y) {
    if(depth[x] < depth[y]) swap(x, y);
    while(depth[x] > depth[y])
        x = fa[x][lg[depth[x]-depth[y]] - 1];
    if(x == y) return x;
    for(int k = lg[depth[x]] - 1; k >= 0; --k)
        if(fa[x][k] != fa[y][k])
            x = fa[x][k], y = fa[y][k];
    return fa[x][0];
}
int main() {
    int n, m, s; scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= n-1; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    for(int i = 1; i <= n; ++i)
        lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    dfs(s, 0);
    for(int i = 1; i <= m; ++i) {
        int x, y; scanf("%d%d",&x, &y);
        printf("%d\n", LCA(x, y));
    }
    return 0;
}

ST表 区间最值

学习博客：算法学习笔记(12): ST表 - 知乎 (zhihu.com)

代码模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// ST https://www.luogu.com.cn/problem/P3865
const int N = 1e5 + 10;
int f[N][21]; // 用来记录 i 到 i + 2 ^ j - 1 区间内的最值 
int Log2[N];
void solve()
{
    int n,m; cin>>n>>m;
    for(int i = 1;i<=n;i++)  cin>>f[i][0];
    
    // 使用st表进行预处理
    for(int i = 1;i<=20;i++)
        for(int j = 1;j +(1 << i) - 1 <= n;j++)
            f[j][i] = max(f[j][i - 1],f[j + (1 << (i - 1))][i - 1]);
    
    // 递推Log
    for(int i = 2;i<=n;i++) Log2[i] = Log2[i / 2] + 1;
    
    for(int i = 0;i<m;i++){
        int l,r; cin>>l>>r;
        int m = 0;
        int s = Log2[r - l + 1];
        m = max(f[l][s],f[r - (1 << s) + 1][s]);
        cout<<m<<endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t = 1;  // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}