- $\text{update 2023.11.14}$：增加 $\text{LCA}$ 求解树上最短路的代码。
$\text{RMQ}$ 定义：区间最值查询，功能类 $\text{st}$ 表，预处理 $O(n\log_2n)$，查询 $O(q)$，总复杂度 $O(n \log _2n+q)$。
$\text{LCA}$ 定义：对于一个有根树 $T$，对于任意两点 $u,v$，找到一个离根最远的节点 $x$，使得 $x$ 同时是 $u,v$ 的祖先，则 $x$ 便是 $u,v$ 的最近公共祖先。
应用场景：对于一个有根树 $T$，求任意两点 $u,v$ 的最短距离（唯一无重复路径）。将其称为从 $u$ 到 $v$ 的简单路径。
$\pm1 \text{RMQ}$：约束 $\text{RMQ}$，其特殊性质体现在，对于任意 $a_i (i\in[1,n))$，都满足 $a_{i+1}-a_i=\pm1$，复杂度 $O(n +q)$。
| 算法名称 | 针对问题 |难度 | 在/离线 | 预处理时间 | $q$ 次询问时间 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $\text{st}$ 表 | 一般 $\text{RMQ}$ | 容易 | 在线 | $O(n \log_2n)$ | $O(q)$ |
| 分块 | 动态 $\text{RMQ}$ | 容易 | 在线 | $O(n)$ | $O(q\sqrt n)$ |
| 线段树 | 动态 $\text{RMQ}$ | 较难 | 在线 | $O(n)$ | $O(q \log_2n)$ |
| 树上倍增 | $\text{LCA}$ | 较易 | 在线 | $O(n \log_2n)$ | $O(q \log_2n)$ |
| $\text{tarjan}$ | $\text{LCA}$ | 较易 | 离线 | | $O(n+q)$ |
| $\pm1\text{RMQ}$ 算法 | $\pm1\text{RMQ}$ | 一般 | 离线 | $O(n)$ | $O(q)$ |
## $\text{st}$ 表求 $\text{RMQ}$
### 预处理
采用 $\text{dp}$ 思想，定义 $f(i,j)$ 表示 $\min\{a_i,a_{i+1},...,a_{i+2^j-1}\}$，其中显然有 $j\le\log_2n$。
例如：$f(1,0)$ 表示 $a_1$，$f(1,2)$ 表示 $\min\{a_1,...,a_4\}$，$f(2,3)$ 表示 $\min\{a_2,...,a_9\}$。
显然有 $f(i,0)=a_i$，这是显然的。
### 状态转移方程
$f(i,j)=\min \{f(i,j-1),f(i+2^{j-1},j-1)\}$。
```cpp
//1<<20 超 10^6，已是目前 1 秒处理的极限
int minST[MAXN][20];
void InitMinST(int a[],int n) {
for(int i=0;i<=n;i++) minST[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++) {
for(int i=0;i+(1<<j)-1<=n;j++) //[i,j] i 起，i+1<<j-1 为终点
minST[i][j]=min(minST[i][j-1],minST[i+(1<<(j-1))][j-1]);
}
return;
}
```
### 查询
求 $\min\{a_s,...,a_t\}$，只需找到一个 $k_{\max}$ 使得 $2^k\le t-s+1$，求 $\min\{f(s,k),f(t-2^k+1,k)\}$，因前面已经预处理出 $f(i,j)$，所以查询 $1$ 次的时间复杂度 $O(1)$ 的。
```cpp
int RMQMIN(int s,int t) {
int k=(int)(log2(t-s+1.0));
return min(minST[s][k],minST[t-(1<<k)+1][k]);
}
```
## 分块求 $\text{RMQ}$
将数组分为长度为 $\sqrt n$ 的若干块，将一个 $[s,t]$ 分为前后两个散块，与中间个数不超过 $\sqrt n$ 的整块，将整个数组遍历一遍求出块中的最小值即可，时间复杂度 $O(n)$。
## 分块求动态 $\text{RMQ}$
加入懒惰标记，如果有 $[s,t]$ 整个区间加上 $k$，则将收尾两个散块加上 $k$，最多 $2\sqrt n$，将中间整块的懒惰标记直接加上 $k$ 即可，因为整块都加上了 $k$，则起最小值也加上 $k$，整块个数不超过 $\sqrt n$，故总的时间复杂度为 $O(2 \sqrt n+\sqrt n)=O(\sqrt n)$。
## 树上倍增 $\text{LCA}$
朴素思想：将 $u$ 与 $v$ 上移，当其重合是则重合的点为 $u$ 与 $v$ 的最近公共祖先。
## 倍增思想
假设 $u$ 与 $v$ 已被调整到等深，则二分往上跳的长度。
- 无交汇：然不行，直接往前跳；交汇：不需要调。
定义 $fa[u][j]$ 表示 $u$ 的 $2^j$ 级祖先，即向上跳 $2^j$ 步的节点。
首先用 $fa$ 数组将 $u$ 跳到与 $v$ 等深度。
- 特殊情况：若跳完之后 $u=v$，则 $\text{LCA(}u,v)=u$。
否则二分跨度，规则同上，显然最多跳 $\log_2n$ 次，即时间复杂度不超过 $O(\log_2n)$。
最后输出二分得到的节点的**父节点**即可。
```cpp
int dep[MAXN],fa[MAXN][20];
int q[MAXN],f,r;
void InitLCA(int rt) {//BFS
int u,v;f=r=0;
memset(fa,-1,sizeof(fa));
dep[rt]=1,q[r++]=rt;
while(f<r) {
u=q[f++];
for(int i=h[u];i;i=e[i].p) {
v=e[i].v;
if(v==fa[u][0]) continue;
fa[v][0]=u,dep[v]=dep[u]+1;
for(int j=1;j<20;j++) {
if(fa[v][j-1]!=-1) fa[v][j]=fa[fa[v][j-1]][j-1];
else break;
}
q[r++]=v;
}
}
return;
}
```
### 查询
```cpp
int QLCA(int u,int v) {
if(dep[u]<dep[v]) swap(u,v);
int delta=dep[u]-dep[v];
for(int i=0;i<20;i++)
if((1<<i)&delta) u=fa[u][i];
if(u==v) return v;
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
```
例子：$\text{dep}[u]-\text{dep}[v]=10_{10}=1010_2$。
跳两次，分别跳 $8$ 次与 $2$次，即 $10$ 转为二进制时为 $1$ 的二进制位。
## $\text{tarjan}$ 求 $\text{LCA}$
集合内的所有结点与当前结点的 $\text{LCA}$ 都是集合的代表元（也是集合中所有结点在原树上的结点）。
- 当前结点：当前遍历结点。
- 死结点：若 $u$ 的所有子节点都已经遍历完了，且 $u$ 点已回溯，则称 $u$ 点为死结点。
- 活结点：正在遍历 $u$ 的子树，则成 $u$ 为活结点。
并查集：代表元：唯一的活节点；死节点：集合内的元素，且不能作为代表元。
按先序遍历进行遍历，主要方法就是用并查集实现（子并父）。
```cpp
int f[MAXN];
void InitBCJ(int n) {
for(int i=0;i<=n;i++) f[i]=i;
}
int Find(int x) {
return x==f[x]?x:f[x]=Find(f[x]);
}
int Union(int x,int y) {//注意将 y 合并到 x
int a=Find(x),b=Find(y);
if(a==b) return a;
return f[b]=a;//子并父
}
```
## 询问前向星
对于一个 $(u,v)$ 询问，分别保存给 $u$ 和 $v$。
同时，记录询问编号，以便于输出。
```cpp
int qh[MAXN],qcnt;
struct Query{int v,p,num;} q[MAXN];
void AddQuery(int u,int v,int num) {
q[++qcnt].v=v; q[qcnt].num=num;
q[qcnt].p=qh[u]; qh[u]=qcnt;
}
```
```cpp
int vis[MAXN],lca[MAXN];
void InitLCA(int n) {
qcnt=0;InitBCJ(n);memset(lca,-1,sizeof(lca));
}
void Tarjan(int u,int fa) {
vis[u]=1; int v;
for(int i=qh[u];i;i=q[i].p)
if(vis[q[i].v]) lca[q[i].num]=Find(q[i].v);
for(int i=h[u];i;i=e[i].p) {
v=e[i].v;
if(v==fa) continue;//无向边回边
Tarjan(v,u); Union(u,v);//并查集父并子
}
}
```
补充：
## $\text{LCA}$ 求解树上最短路 $\text{(travel)}$
贴个代码，应该不难理解。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=25;
int deep[N],fa[N][M],rd[N],h[N],vis[N],city[N],qcnt;
struct Query{int v,p;} e[N];
queue <int> q;
void AddQuery(int u,int v) {
e[++qcnt].v=v;
e[qcnt].p=h[u]; h[u]=qcnt;
}
int read() {
int f=1,s=0;
char c=getchar();
while((c<'0'||c>'9')&&c!='-') c=getchar();
if(c=='-') f=-1;
else s+=c-'0';
c=getchar();
while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
return s*f;
}
int main() {
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
memset(fa,-1,sizeof(fa));
int n=read(),m,root=1,u,v,ans=0;
deep[1]=1;
for(int i=1;i<n;i++) {
u=read(),v=read();rd[v]++;
deep[v]=deep[u]+1,fa[v][0]=u;
AddQuery(u,v),AddQuery(v,u);
}
m=read();
for(int i=1;i<=m;i++) city[i]=read();
q.push(root),vis[root]=1,deep[root]=1;
while(!q.empty()) {
int tmp=q.front();q.pop();
for(int i=h[tmp];i;i=e[i].p) {
v=e[i].v;
if(vis[v]) continue;
fa[v][0]=tmp,deep[v]=deep[tmp]+1;
for(int j=1;j<20;j++) {
if(fa[v][j-1]!=-1) fa[v][j]=fa[fa[v][j-1]][j-1];
else break;
}
q.push(v),vis[v]=1;
}
}
for(int i=1;i<m;i++) {
int LCA;
u=city[i],v=city[i+1];
if(deep[u]<deep[v]) swap(u,v);
int delta=deep[u]-deep[v];
for(int i=0;i<20;i++) if((1<<i)&delta) u=fa[u][i];
if(u==v) LCA=v;
else {
for(int i=19;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
LCA=fa[u][0];
}
ans+=deep[city[i]]+deep[city[i+1]]-2*deep[LCA];
}
cout<<ans;
return 0;
}
/*
1
/ \
2 5
/ \
3 4
*/
```
## 最大整除区间 $\text{(div)}$
给出一个序列 $\{a\}$，希望找到一对数 $(l,r)$ 符合一下条件：
- 存在 $l\le j\le r$，使得 $a_j|a_{i\in[l,r]}$。
- 在上个条件的所有 $(l,r)$ 中，$r-l$ 应该去最大值。
输出：第一行为满足条件的数对数量及 $\max\{r-l\}$，第二行分别输出最优数对 $(l,r)$ 中的 $l$ 值。
显然，若令 $x=\min\{a_{i\in[l,r]}\},y=\gcd(a_{i\in[l,r]})$
，则显然若 $x|y$，即 $x=y$，因为显然 $y\le x$，则符合条件，再二分处理答案即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=25;
int n,minn[N][M],gcd[N][M],print[N],a[N];
int read() {
int f=1,s=0;
char c=getchar();
while((c<'0'||c>'9')&&c!='-') c=getchar();
if(c=='-') f=-1;
else s+=c-'0';
c=getchar();
while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
return s*f;
}
int check(int x) {
int tmp=log2(x);
if(tmp<0) return 0;
int cnt=0;
for(int i=1;i+x<=n;i++) {
int tmp1=min(minn[i][tmp],minn[i+x-(1<<tmp)+1][tmp]);
int tmp2=__gcd(gcd[i][tmp],gcd[i+x-(1<<tmp)+1][tmp]);
if(tmp1==tmp2) print[++cnt]=i;
}
return cnt;
}
int main() {
freopen("div.in","r",stdin);
freopen("div.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) minn[i][0]=gcd[i][0]=a[i];
for(int j=1;j<20;j++) {
for(int i=1;i+(1<<(j-1))<=n;i++) {
minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
gcd[i][j]=__gcd(gcd[i][j-1],gcd[i+(1<<(j-1))][j-1]);
}
}
int l=0,r=n,ans=0;
while(l!=r) {
int mid=ceil((l+r)/2.0);
int tmp=check(mid);
if(tmp) l=mid,ans=tmp;
else r=mid-1;
}
if(!l) {ans=n;for(int i=1;i<=n;i++) print[i]=i;}
cout<<ans<<" "<<l<<"\n";
for(int i=1;i<=ans;i++) printf("%d",print[i]);
return 0;
}
```