文章目录
展开0.前言
本章节将讲述RMQ（区间最值问题），ST表，LCA（最近公共祖先）以及树链剖分相关知识。
以及会针对具体问题讨论树上差分。
废话不多说，让我们开始本章的内容吧。
1.RMQ
1.1 问题描述
RMQ的模板问题是指：给你一个数组，其中有N(1 \leq N \leq 50000)个数字，现在给你Q(1 \leq Q \leq 200000)次询问，每次询问区间[l,r]内的最大值。
1.2 问题分析
最朴素的办法是暴力，但是暴力的时间复杂度是O(NQ)，很显然会TLE。
1.2.1 预处理
那么我们来考虑一种DP预处理算法。
设a[i]是给定的数组，f[i,j]表示从第i个数起连续2^j个数中的最大值（注意我们的状态不是表示区间[i,j]的最大值，因为这个状态的复杂度是O(n^2)的，也不足够优秀）。
我们举个例子：数列a为{6,1,8,3,5,9,2,4,10,7}。
那么f[1,0]=max{6}=6，f[1,1]=max{6,1}=6，f[1,2]=max{6,1,8,3}=8，f[1,3]=max{6,1,8,3,5,9,2,4}=9。这样我们就可以理解状态的含义了。
DP三要素：状态、初态、转移方程。
我们来考虑初态，即f[i,0]=max{a[i]}=a[i](0\leq i< n)。
最后是转移方程：
对于f[i,j]，当j>0时（此时表示的区间内一定有偶数个数字），我们将其均分成两段，分别是f[i,j-1]和f[i+2^{(j-1)},j-1]。因此我们得到状态转移方程f[i,j]=max(f[i,j-1],f[i+2^{(j-1)},j-1])。
这样我们可以通过O(nlogn)的时间将所有区间的最大值初始化出来。
1.2.2 查询
要想查询区间[l,r]的最大值，那么我们就要找到能覆盖这个区间的幂次。
也就是说，我们要找到一个k，使得区间[l,l+2^k-1]和区间[r-2^k+1,r]有交集。
因此我们要满足如下条件：l\leq r-2^k+1，l+2^k-1 \leq r，r-2^k+1 \leq l+2^k-1。
解得：k \leq log_2(r-l+1)且k \geq log_2(\frac{r-l}{2}+1)。
可证，取k=\lfloor log_2(r-l+1) \rfloor满足上式。
因此，查询区间[l,r]的最大值，即为max(f[l,k],f[r-2^k+1][k])。
单次查询时间复杂度为O(1)。
1.3 例题
1.3.1 洛谷P3865 【模板】ST 表
这是一道RMQ的模板题，我们可以用这道题具体来实现上述讲解。
ST表代码：
|
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 |
#include <iostream> #include <cmath> using namespace std; int n,m,l,r; int a[100010]; int f[100010][25]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i][0]=a[i]; } for(int k=1;(1<<k)<=n;k++) { for(int i=1;i+(1<<k)-1<=n;i++) f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]); } while(m--) { scanf("%d%d",&l,&r); int k=log2(r-l+1); printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k])); } return 0; } |
在我们具体实现时，要注意k和i的枚举顺序。应该是先枚举k后枚举i，因为我们要先修改小区间才能逐步扩展到大区间。还需注意k和i的枚举范围，不要超出数组长度。
1.3.2 洛谷P1440 求m区间内的最小值
这道题有很多种解法，我们就只考虑用RMQ解，查询是区间[i-m,i-1](1 \leq i \leq n)。
RMQ代码：
|
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 |
#include <iostream> #include <cmath> using namespace std; int n,m,x; int f[2000001][22]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); f[i][0]=x; } for(int k=1;(1<<k)<=n;k++) { for(int i=1;i+(1<<k)-1<=n;i++) f[i][k]=min(f[i][k-1],f[i+(1<<(k-1))][k-1]); } printf("0\n"); for(int i=2;i<=n;i++) { int l=max(1,i-m),r=i-1; int k=log2(r-l+1); printf("%d\n",min(f[l][k],f[r-(1<<k)+1][k])); } return 0; } |
大家按照上面的代码写完后，会发现只能得80分，有两个点MLE了。
所以我们要考虑优化空间，DP中优化空间的方法就是滚动数组了。
有关滚动数组的知识会在后续DP专题中介绍，先贴一个博客，大家可以进行参考。
RMQ+滚动数组的代码如下：
|
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 |
#include <iostream> #include <cmath> using namespace std; int n,m,x; int f[2000010][2]; int main() { scanf("%d%d",&n,&m); int t=0,j=2; printf("0\n"); for(int k=0;(1<<k)<=n;k++) { t=1-t; if(k==0) { for(int i=1;i<=n;i++) { scanf("%d",&x); f[i][t]=x; } } else { for(int i=1;i+(1<<k)-1<=n;i++) f[i][t]=min(f[i][1-t],f[i+(1<<(k-1))][1-t]); } while(j<=n&&min(j-1,m)<(1<<(k+1))) { int l=max(1,j-m),r=j-1; int k=log2(r-l+1); printf("%d\n",min(f[l][t],f[r-(1<<k)+1][t])); j++; } } return 0; } |
对于这道题，大家只需要暂时掌握第一种写法，即只用RMQ的写法。至于滚动数组，可以等以后具体学习后再来完善。
1.4 总结
我们再来重新考虑这道题，发现区间求值类的问题好像线段树也能求解，但是线段树的区间修改区间查询都是O(logn)的，当查询次数m极高时，会出现复杂度O(mlogn)爆时间的情况。而RMQ仅需要O(nlogn)的复杂度初始化，然后O(1)查询即可，优化了时间。
上面我们构造的状态f[i][j]就是ST表。所以我们可以将ST表视作解决RMQ问题的工具。具体区分就是ST表示方法，而RMQ是问题。
2. LCA（Least Common Ancestors）
2.1 问题描述
洛谷P3379 【模板】最近公共祖先（LCA）题目链接
给定一颗有根多叉树，求出指定两个点的最近公共祖先。
最近公共祖先：层数最大（深度最深）的公共祖先。
一般会有多组提问，即M组提问，每组提问给定两个点，求这两个点的最近公共祖先。
LCA问题有很多种解法，我们一个一个来分析。
2.2 离线Tarjan算法
离线算法指先存下所有的询问，然后将这些询问按处理顺序解答，最后统一输出答案的方法。这种算法需要我们事先知道问题，对于动态给出的问题便不适用。
本算法利用了并查集技术和树的后序遍历技术。
我们每遍历一个结点，首先遍历这个结点的所有子树。当存在某次询问的两个结点都在以本结点为根的子树内时，这次询问的答案就是本节点。
|
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 63 64 65 66 67 68 |
#include <iostream> using namespace std; int n,m,s,u,v; int f[500010]; int head[500010],to[1000010],nxxt[1000010],cnt=0; bool vis[500010]; int ans[500010]; int qhead[500010],qto[1000010],qnxxt[1000010],qcnt=0; void add(int u,int v) { to[++cnt]=v; nxxt[cnt]=head[u]; head[u]=cnt; } void qadd(int u,int v) { qto[++qcnt]=v; qnxxt[qcnt]=qhead[u]; qhead[u]=qcnt; } int find(int x) { if(x==f[x])return x; return f[x]=find(f[x]); } void Tarjan(int u) { vis[u]=true; for(int i=head[u];i;i=nxxt[i]) { int v=to[i]; if(vis[v])continue; Tarjan(v); f[v]=u; } for(int i=qhead[u];i;i=qnxxt[i]) { int v=qto[i]; if(!vis[v])continue; int a=find(v); ans[(i+1)/2]=a; } } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) { f[i]=i; vis[i]=false; } for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); qadd(u,v); qadd(v,u); } Tarjan(s); for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; } |
2.3 转化为RMQ解决LCA
RMQ问题已经讲过，如何将LCA转换成RMQ是我们要思考的。
树上的任意两点间都有且仅有一条路，而两点的最近公共祖先是路上深度最小的点。
对于LCA转化为RMQ，我们需要记录欧拉序列，深度序列和每个点在欧拉序中第一次出现的位置序列。
树的欧拉序列是在对树进行DFS时，记录经过的每一个结点。
我们给出一个树的例子：
这棵树的欧拉序如下图第一行：
那么上图第二行是什么呢？是对应结点的深度。
这样，我们只需要最后记录任意两个点之间的路径怎么找就可以了。
我们记录每个点第一次被访问的次序（这个辅助序列只是方便我们快速查询到某个节点在欧拉序里的位置）：
这样，我们需要找到对应结点间欧拉序列的点的深度的最小值。
虽然欧拉序列中很多点会出现多次，或者出现子树等等，但这对我们找深度最小的点是没有影响的。
比如上图的8和11，中间的跨度从欧拉序下标8到欧拉序下标20，虽然理论上两个点的路径为8-6-3-7-11，但是其他若干个点的深度都比两者LCA的深度要大。因此，我们可以直接求这个区间内的深度最小的点。
|
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 <iostream> #include <cmath> using namespace std; int n,m,s,u,v; int head[500010],to[1000010],nxxt[1000010],cnt=0; int phi[1000010],dep[1000010],first[500010],pcnt=0; int f[1000010][25]; void add(int u,int v) { to[++cnt]=v; nxxt[cnt]=head[u]; head[u]=cnt; } void dfs(int x,int d) { phi[++pcnt]=x; first[x]=pcnt; dep[pcnt]=d; for(int i=head[x];i;i=nxxt[i]) { int v=to[i]; if(!first[v]) { dfs(v,d+1); phi[++pcnt]=x; dep[pcnt]=d; } } return ; } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(s,1); for(int i=1;i<=pcnt;i++)f[i][0]=i; for(int k=1;(1<<k)<=pcnt;k++) { for(int i=1;i+(1<<k)-1<=pcnt;i++) { int x1=f[i][k-1],x2=f[i+(1<<(k-1))][k-1]; if(dep[x1]<dep[x2])f[i][k]=x1; else f[i][k]=x2; } } while(m--) { scanf("%d%d",&u,&v); int l=min(first[u],first[v]),r=max(first[u],first[v]); int k=log2(r-l+1); int x1=f[l][k],x2=f[r-(1<<k)+1][k]; if(dep[x1]<dep[x2])printf("%d\n",phi[x1]); else printf("%d\n",phi[x2]); } return 0; } |
这种算法的理解还算简单，但是代码实现起来会遇到很多问题，如果RMQ模板不熟练的话建议先多敲几遍RMQ的模板题，尽量做到“肌肉记忆”。这种算法的实现难度还是很大的，相当于将求树的欧拉序和RMQ两道问题进行合并。但还是需要掌握的。
2.4 倍增LCA
我们先考虑一种朴素的求解方法：我要一步一步往上爬。
我们先把x和y弄到同一深度，然后同时一步一步往上找，直到找到共同的人，它就是x和y的LCA。
但是这种方法时间复杂度极其极其高，毕竟是蜗牛嘛。
所以我们考虑倍增。
何为倍增，就是翻倍增加。你一次向上找一个慢，那我就一次向上找到2^i。
我们首先预处理出表f[i][j]，表示结点i向上走2^j步的结点。易得f[i][0]为结点i的父亲。
预处理的方法也很简单，f[i][j]=f[f[i][j-1]][j-1]。
当然我们还需要预处理出每个结点的深度记在数组depth中。
我们爬的时候是从大距离到小距离爬，因为如果从小到大爬，假设爬五层遇到了LCA，但是你却是爬了1+2+4，总是遇不到LCA的，而从大向小爬就能爬到4+1。这里的表述不是很清晰，大家可以自己爬一爬看看。
我们真正求解是碰到爬完后遇到的人相等的时候先不管，如果两个人都跳了8个距离，遇到的人相等，并不能确定下面有没有人还满足LCA，所以只能求出CA。
|
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 |
#include <iostream> #include <cmath> using namespace std; int n,m,s,u,v; int head[500010],to[1000010],nxxt[1000010],cnt=0; int d[500010],f[500010][25]; void add(int u,int v) { to[++cnt]=v; nxxt[cnt]=head[u]; head[u]=cnt; } void dfs(int u,int fa) { d[u]=d[fa]+1; f[u][0]=fa; for(int i=1;(1<<i)<=d[u];i++) f[u][i]=f[f[u][i-1]][i-1]; for(int i=head[u];i;i=nxxt[i]) { int v=to[i]; if(v!=fa) dfs(v,u); } } int lca(int a,int b) { if(d[a]>d[b])swap(a,b); for(int i=20;i>=0;i--) { if(d[a]<=d[b]-(1<<i))//先让b爬到跟a一样的高度上 b=f[b][i]; } if(a==b)return a; for(int i=20;i>=0;i--) { if(f[a][i]==f[b][i])//真正找的时候遇到CA也不管 continue; a=f[a][i]; b=f[b][i]; } return f[a][0];//最后两个人一定爬到LCA的下一层，输出任意一个人的父亲即可 } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(s,0); while(m--) { scanf("%d%d",&u,&v); printf("%d\n",lca(u,v)); } return 0; } |
当然，写法可能千奇百怪，但是思想是共同的。
2.5 树剖LCA
挖坑待填。
3.树上差分
挖坑待填。