一.RMQ1.RMQRMQ即区间查询是指这样一个问题:对于长度为n的数列A回答若干次询问RMQ(A,i,j),返回数列中下标在i,j之间的最小/大值。2.符号约定假设一个算法预处理时间为f(n),查询时间为g(n),这个算法的复杂度记为f(n),g(n)RMQA(i,j)来表示数组A中索引i和j之间最小值的位置3.RMQ相关算法(1)在线暴力遍历算法:假设数据的规模:N,查询数:Q单次查询时间复杂度:O(N)总的时间复杂度:O(N*Q)(2)预处理直接查询预处理:枚举所有区间然后每个区间遍历查找之后f[i][j]表示区间[i,j]之间的最小值复杂度:O(N^3),O(1)(3)预处理的DP优化复杂度:O(N^2),O(1)而且空间复杂度也是O(N^2)优缺点:查询效率高预处理效率太低(4)线段树复杂度:O(n),O(logn)(5)分块算法(6)ST表算法二.ST表ST表中M数组的含义M[i][j],表示从下标i开始长度为2^j的子数组的最小值的索引ST表算法的DP预处理把 M [i][j] 对应的区间平均分成两段M [i][j] 对应的区间长度一定为偶数从 i 到为前一段到为后一段 (长度都为)则 M [i][j] 就是这两段的最小值中的最小值对应的索引。可得 DP 状态转移方程if(a[M[i][j-1]] a[M[i2^{j-1}][j-1]]) M[i][j] M[i][j-1]else M[i][j] M[i2^{j-1}][j-1]其中初始化M [i][0] iST表算法的查询实现预处理M[i][j]完成以后如何进行RMQA(i,j)查询查询实现选择两个能够完全覆盖区间[i..j]的块并且找到它们之间的最小值。设k [log₂(j-i1)](向下取整)则得if(a[M[i][k]] a[M[j-2ᵏ1][k]]) RMQA(i,j) M[i][k],else RMQA(i,j) M[j-2ᵏ1][k]M[i][k]——从查询区间起始点i开始向后长度为2ᵏ的一段M[j-2ᵏ1][k]——从查询区间尾j开始向前长度为2ᵏ的一段算法复杂度O(NlogN), O(1)#includebits/stdc.h using namespace std; class ST { public: ST(int n,vectorinta):M(n1,vectorint((int)log2(n)1)) { pre(a); } void pre(vectorinta) { //初始化 int n a.size() - 1; for (int i 1; i n; i) { M[i][0] i; } //预处理M数组 for (int j 1; (1 j) n; j) {//枚举区间长度 for (int i 1; (i(1j)-1)/*保证右端点不越界*/ n; i) {//枚举起点 int tmp (1 (j - 1));//一半长度 if (a[M[i][j - 1]] a[M[i tmp][j - 1]]) { M[i][j] M[i][j - 1]; } else { M[i][j] M[i tmp][j - 1]; } } } } int search(int l, int r,vectorinta) { int k log2(r - l 1); int tmp (1 k); return max(a[M[l][k]], a[M[r-tmp1][k]]); } public: //M:从i位置开始往后2^j的RMQ vectorvectorintM; }; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m; cin n m; vectorinta(n1); for (int i 1; i n; i) { cin a[i]; } ST s(n,a); while (m--) { int l, r; cin l r; couts.search(l, r, a)\n; } return 0; }ST表算法小结常用于解决RMQ问题(最值GCDLCM等等)适用于静态数据的查询(不支持修改)经过一次O(nlog2n)的离线预预处理之后单次查询O(1)所以ST算法尤其适用于查询量很大很大的问题。例题数列连续区间gcd的特点单调性(非增)!!!!!推荐算法:ST求gcd二分预处理所有gcdmap存储方案数三.LCA1.LCA概念LCA,即最近公共祖先是指这样一个问题:在有根树中找出某两个节点u和v最近的公共祖先(换一种说法离树根最远的祖先)。生活中的的LCA:家族树状图LCA和RMQ问题的关系2.符号约定3.例子4.LCA相关算法(1)暴力算法分别从节点 u 和 v 回溯到 T 的根节点获取 u 和 v 到根节点的路径 P1P2其中 P1 和 P2 可以看成两条单链表。然后依次判断 P1 中的每个节点是否在 P2 中出现第一个出现在 P2 中的节点即为第一个相交节点即 LCAT(u,v)。时间复杂度O (N²)(2)暴力算法2:求两个链表的交点时可以适用hash表优化或者适用跳跃链表时间复杂度:O(N)(3)倍增算法四.倍增算法解决LCA倍增算法求LCA的P数组的含义P[i][i]:表示从节点i往上跳2^i(节点i的第2^i个祖先)倍增算法求LCA的DP预处理P[i][0]father[i];P[i][j]P[P[i][j-1]][j-1];时间复杂度:O(nlogn)为什么一开始要先要初始化P数组为-1因为有可能越界(假如说一共有五层,从叶子节点能最多能跳2^2,但是如果我们从第二层跳2^2就会越界)倍增算法求LCA首先将 x 和 y 中深度较大的那个往上跳到和另一个深度相同。此时如果 xy则 LCA (x,y)x算法结束否则进入下一步。然后同时向上倍增枚举一个 2 的幂的步长 2ⁱ若 x 往上走 2ⁱ步与 y 往上走 2ⁱ步不为同一个点(没跳过)则将它们同时往上走 2ⁱ步如果为同一个点不跳因为只能说明是祖先但不一定是最近公共祖先。循环类似处理i从log2(deep(u))向下取整,逐步缩小 i最后你会发现x和y一定跳到了最近公共祖先的下一层时间复杂度O (NlogN), O (logN)注意:LCA 倍增跳跃必须从大到小枚举二进制拼凑,比如说9如果从大到小枚举就拆成8和1但是如果从小到大枚举就会拆成124(凑不出来8)错误的贪心方式五.LCA 到 RMQ 的规约LCA和RMQ问题本质相同我们可以在线性时间里将 LCA 问题规约到 RMQ 问题。因此每一个解决 RMQ 的算法都可以解决 LCA 问题。从树 T 根节点开始DFS 遍历得到 2n−1 个顶点组成的序列欧拉回路如下表1 2 1 3 5 3 6 8 6 9 6 3 7 10 12 10 13 10 7 11 7 3 1 4 1如果我们想要求任意两点的最近公共祖先实际上就是求两点间dfs序中深度最小的那个节点两点间dfs序是连续数组之后求连续数组的深度的最小值我们可以适用st表来解决六.例题解题思路:注意: