算法知识-倍增算法
一.RMQ
1.RMQ
RMQ，即区间查询，是指这样一个问题:对于长度为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[i+2^{j-1}][j-1]]) M[i][j] = M[i][j-1]
else M[i][j] = M[i+2^{j-1}][j-1]
其中，初始化：M [i][0] = i
ST表算法的查询实现
预处理M[i][j]完成以后，如何进行RMQA(i,j)查询？
查询实现：选择两个能够完全覆盖区间[i..j]的块，并且
找到它们之间的最小值。设k = [log₂(j-i+1)](向下取整)，则得：
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)>
#include<bits/stdc++.h> using namespace std; class ST { public: ST(int n,vector<int>&a):M(n+1,vector<int>((int)log2(n)+1)) { pre(a); } void pre(vector<int>&a) { //初始化 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+(1<<j)-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,vector<int>&a) { int k = log2(r - l + 1); int tmp = (1 << k); return max(a[M[l][k]], a[M[r-tmp+1][k]]); } public: //M:从i位置开始，往后2^j的RMQ vector<vector<int>>M; }; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; vector<int>a(n+1); for (int i = 1; i <= n; i++) { cin >> a[i]; } ST s(n,a); while (m--) { int l, r; cin >> l >> r; cout<<s.search(l, r, a)<<'\n'; } return 0; }ST表算法小结
常用于解决RMQ问题(最值，GCD，LCM等等)
适用于静态数据的查询(不支持修改)，经过一次O(nlog2n)的离线预预处理之后，单次查询O(1)
所以，ST算法尤其适用于查询量很大很大的问题。
例题
数列连续区间gcd的特点？
单调性(非增)!!!!!
推荐算法:
ST求gcd+二分预处理所有gcd+map存储方案数
三.LCA
1.LCA概念
LCA,即最近公共祖先，是指这样一个问题:在有根树中，找出某两个节点u和v最近的公共祖先(换一种说法，离树根最远的祖先)。
生活中的的LCA:家族树状图
LCA和RMQ问题的关系？
2.符号约定
3.例子
4.LCA相关算法
(1)暴力算法
分别从节点 u 和 v 回溯到 T 的根节点，获取 u 和 v 到根节点的路径 P1，P2，其中 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 中深度较大的那个往上跳到和另一个深度相同。
此时，如果 x=y，则 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，但是如果从小到大枚举，就会拆成1，2，4(凑不出来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表来解决
六.例题
解题思路:
注意: