前置知识 -- 倍增
倍增算法，顾名思义，就是不断地翻倍。
虽然是一种基础算法，但它能够使得线性的处理转化为对数级的处理，大大地优化时间复杂度，在很多算法中都有应用，其中最常见的就是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;
}