介绍
从一个有根树中寻找一对节点的最小公共祖先(Lowest common ancestor)的问题，从20世纪就已经被充分研究了，现在已经成为了图论中的基本算法。这个问题之所以有趣，不仅是因为解决算法非常有技巧性，还因为该算法被广泛的应用于字符串处理和计算生物学上，例如，LCA可以使用后缀树或其他树结构解决。Harel and Tarjan第一次研究该问题，他们向我们展示通过用线性时间去处理输入树，每次查询只需要常量时间。他们的工作已经被后人扩展了，本教程将为读者展示许多可以用于其他问题的有趣算法。
RMQ算法以数组作为底层数据结构，在特定的区间中，发现具有最小元素的位置。再文章后面，我们将会看到LCA问题可以转化为RMQ问题的受限版本(与generalized相对)。RMQ不仅可以用于LCA，还可以用于字符串预处理，字符串预处理使用后缀数组(一个新的支持字符串查询的数据结构，可以替代后缀树，但会使用更少的内存，且容易编程实现)
本教程，将先介绍RMQ。我们将先介绍一些效率不高，但容易编程实现的方法，来解决RMQ问题。然后介绍LCA和RMQ之间的关系，我们将先回顾两个解决LCA问题的简单方法，然后说明RMQ等价于LCA问题。最后，我们将会看到RMQ问题如何转化为它的受限版本，以及用于受限版本的快速算法。
记号
算法的预处理时间记为f(n)， 查询时间记做g(n). 算法的整体复杂度记做<f(n), g(n)>
在某个数组A上，位于区间i和j之间的最小值的位置记做 RMQA(i, j)
在有根节点树T上，距离根节点最远的且是节点u和v的共同祖先的节点 记做 LCAT(u, v)
Range Minimum Query(RMQ)
给定数组A[1, N-1], 寻找在给定区间上最小元素的位置。
RMQ的平凡算法
使用二维数组M[0, N-1][0, N-1]存储区间[i, j]的RMQA(i, j)值.
显然平凡算法的时间复杂度<O(N3, O(1))>。然而我们可以使用动态规划的方法将复杂度减少到<O(N2, O(1))>.
代码如下:
void process1(int M[MAXN][MAXN], int A[MAXN], int N)
{
int i, j;
for (i =0; i < N; i++)
M[i][i] = i;
for (i = 0; i < N; i++)
for (j = i + 1; j < N; j++)
if (A[M[i][j - 1]] < A[j])
M[i][j] = M[i][j - 1];
else
M[i][j] = j;
}
一个<O(N), O(sqrt(N))>方法
思路是将数组A分成sqrt(N)的部分，然后使用数组M[0, sqrt(N)-1]存储这些部分的最小值 （见下图）。显然，只需要扫描一遍数组A，就可以完成预处理。但查询，要稍微花费点力气。
查询RMQA(i, j): 思路就是从sqrt(N)个部分和与区间[i, j]交叉的区间计算出。比如RMQA(2, 7), 我们需要比较 A[2], A[M[1]], A[6], A[7]的大小，然后得到最小值的位置。显然每次计算最多有3 x sqrt(N)次比较操作.
该算法的优点：快速编码，可以调整为动态版本（在两次查询之间可以改变数组元素）.
稀疏表算法(Sparse Table (ST) algorithm)
预处理RMQ的更好方法就是利用动态规划的方法，对长度为2k的子数组预处理。 我们使用数组M[0, N-1][0, Log(N)]存储结果，M[i][j]存储从位置i开始，长度为2j的子数组中最小值的位置。例如，
当计算M[i][j], 我们必须查找 区间的前半部分最小值的位置 M[i][j-1] 和区间的后半部分的最小值的位置 M[i+2j-1-1][j-1].
预处理代码如下:
void process2(int M[MAXN][LOGMAXN], int A[MAXN], int N)
{
int i, j;
//initialize M for the intervals with length 1
for (i = 0; i < N; i++)
M[i][0] = i;
//compute values from smaller to bigger intervals
for (j = 1; 1 << j <= N; j++)
for (i = 0; i + (1 << j) - 1 < N; i++)
if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
M[i][j] = M[i][j - 1];
else
M[i][j] = M[i + (1 << (j - 1))][j - 1];
}
查询RMQA(i, j): 思路就是选出两个可以覆盖区间[i,j]的块，找出其中最小的。令 k = [log(j-i+1)]
时间复杂度<O(Nlog(N), O(1))>
区间树
RMQ问题也可是使用区间数解决，区间数是一个堆状的数据结构，可以用log时间上执行快速更新和查询操作，我们用递推的方式定义位于区间[i, j]的区间树如下:
- 第一个节点存放区间[i,j ]的信息。
- 如果 i < j, 左右孩子分别存放区间[i, (i+j)/2]和[(i+j)/2+1, j]的信息。
例如
使用区间树解决RMQ问题，我们需要使用数组 M[1, 2 x 2[logN]+1]存储区间树的信息，M[i]表示区间树第i个节点的最小值的索引信息。
void initialize(int node, int b, int e, int M[MAXIND], int A[MAXN], int N)
{
if (b == e)
M[node] = b;
else
{
//compute the values in the left and right subtrees
initialize(2 * node, b, (b + e) / 2, M, A, N);
initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N);
//search for the minimum value in the first and
//second half of the interval
if (A[M[2 * node]] <= A[M[2 * node + 1]])
M[node] = M[2 * node];
else
M[node] = M[2 * node + 1];
}
}
查询区间[i, j]的最小值索引
int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, int j)
{
int p1, p2;
//if the current interval doesn't intersect
//the query interval return -1
if (i > e || j < b)
return -1;
//if the current interval is included in
//the query interval return M[node]
if (b >= i && e <= j)
return M[node];
//compute the minimum position in the
//left and right part of the interval
p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);
//return the position where the overall
//minimum is
if (p1 == -1)
return M[node] = p2;
if (p2 == -1)
return M[node] = p1;
if (A[p1] <= A[p2])
return M[node] = p1;
return M[node] = p2;
}
我们应该使用参数为 node=1, b=0, e=N-1调用该函数，因为第一个节点覆盖的区间是[0, N-1]。
时间复杂度: <O(N), O(logN)>
区间树优点：灵活的数据结构，可以用于RMQ问题的动态版本，在区间搜索问题也有很多广泛的应用。
最小公共祖先(Lowest Common Ancestor, LCA)
一个 <O<N>, O(sqrt(N))>算法
在RMQ问题中，我们将数组区间分成相等的几个部分，在LCA问题中也可以这样做。
具体的，我们将树分成sqrt(H)个部分，H表示树的高度。因此，第一个部分包含的层次在0和sqrt(H)-1之间，第二个部分包含的层次在sqrt(H)和2*sqrt(H)-1之间。例如，
对每个节点node，我们知道其祖先位于节点node所在部分的上一个部分的最后一层. 我们将会预处理，并将信息放在数组P[1, MAXN]中。例如，
位于第一个部分的节点标记为1，P[i]=1.
可以看到，位于部分第一层的节点 都有 P[i]=T[i], 我们可以使用深度搜索预处理数组P( T[i]是节点i的父亲， nr 是 [sqrt(H)], L[i]节点i所在的层)
代码如下：
void dfs(int node, int T[MAXN], int N, int P[MAXN], int L[MAXN], int nr) {
int k;
//if node is situated in the first
//section then P[node] = 1
//if node is situated at the beginning
//of some section then P[node] = T[node]
//if none of those two cases occurs, then
//P[node] = P[T[node]]
if (L[node] < nr)
P[node] = 1;
else
if(!(L[node] % nr))
P[node] = T[node];
else
P[node] = P[T[node]];
for each son k of node
dfs(k, T, N, P, L, nr);
}
寻找LCA，先寻找找到所在部分，然后在计算
int LCA(int T[MAXN], int P[MAXN], int L[MAXN], int x, int y)
{
//as long as the node in the next section of
//x and y is not one common ancestor
//we get the node situated on the smaller
//lever closer
while (P[x] != P[y])
if (L[x] > L[y])
x = P[x];
else
y = P[y];
//now they are in the same section, so we trivially compute the LCA
while (x != y)
if (L[x] > L[y])
x = T[x];
else
y = T[y];
return x;
}
该函数至多需要 2 x sqrt(H)个操作，因此我们的时间复杂度 <O(N), O(sqrt(H))>, 其中 H 是树的高度，最坏情况是当H==N时。
算法的优点：编码简单，快速。
时间复杂度<O(NlogN), O(LogN)>的算法
我们可以使用动态规划解决问题。 我们用二维数组 P[1, N][1, LogN]存储相关信息，P[i][j]表示i的第 2j-th祖先。我们使用下面的递推公式。
预处理算法如下，
void process3(int N, int T[MAXN], int P[MAXN][LOGMAXN])
{
int i, j;
//we initialize every element in P with -1
for (i = 0; i < N; i++)
for (j = 0; 1 << j < N; j++)
P[i][j] = -1;
//the first ancestor of every node i is T[i]
for (i = 0; i < N; i++)
P[i][0] = T[i];
//bottom up dynamic programing
for (j = 1; 1 << j < N; j++)
for (i = 0; i < N; i++)
if (P[i][j - 1] != -1)
P[i][j] = P[P[i][j - 1]][j - 1];
}
时空复杂度：O(NlogN)
查询算法，
令 L[i] 表示节点i的层
如果节点 p 和 q 位于同一层，那么我们可以使用元二分查找计算 LCA(p, q)。
因此，如果 P[p][i] != P[q][i], 那么LCA(p, q)位于更高的层上，我们需要计算 LCA(p=P[p][i], q = P[q][i]), 其中 i 在 log(L[p])和0之间，最后，p和q将具有相同的父亲，返回T[p].
如果 p 和 q 不在同一层，不失一般性，假设 L[p] < L[q], 我们依然可以使用元二分搜索查找p的祖先，使其祖先和q位于同一层上，
int query(int N, int P[MAXN][LOGMAXN], int T[MAXN],
int L[MAXN], int p, int q)
{
int tmp, log, i;
//if p is situated on a higher level than q then we swap them
if (L[p] < L[q])
tmp = p, p = q, q = tmp;
//we compute the value of [log(L[p)]
for (log = 1; 1 << log <= L[p]; log++);
log--;
//we find the ancestor of node p situated on the same level
//with q using the values in P
for (i = log; i >= 0; i--)
if (L[p] - (1 << i) >= L[q])
p = P[p][i];
if (p == q)
return p;
//we compute LCA(p, q) using the values in P
for (i = log; i >= 0; i--)
if (P[p][i] != -1 && P[p][i] != P[q][i])
p = P[p][i], q = P[q][i];
return T[p];
}
可以看到该函数最多运行 2 x Log(H)次操作，其中H是树的高度，最坏情况下发生在H=N的时候
将LCA问题变为RMQ问题
线性时间内，将LCA转为RMQ问题，因此任何用于RMQ的都可以用于LCA问题。我们使用下图，展示如何将LCA转换为RMQ问题。
注意到，LCAT(u, v)是在深度优先搜索中节点u和v的过程中，相遇的节点中的距离根节点最近的节点。
因此，在树的欧拉路径中，我们可以考虑位于节点u和v的索引之间的所有节点，然后查找其中处于最低层的节点。为了做到这点，我们需要三个数组：
- E[1, 2 x N-1] - 树的欧拉路径上的访问过的节点； E[i] 路径中第 i 个访问过的节点。
- L[1, 2 x N-1] - 树的欧拉路径上访问过的节点在树中的层次；L[i] 节点 E[i] 的层次。（第 i 个访问的节点的层次）
- H[1, N] - H[i] 是在 E 中第一次遇到节点 i 的索引（记录节点 i 第几次出现都可以，如果只记录第一次出现的，也没什么问题）
假设 H[u] < H[v] (否则，就交换 u 和 v)。 显然，可以看到在 节点u和v第一次出现的区间之间的节点 是 E[H[u]...H[v]]. 现在，我们必须查找这些节点中处于最低层次的节点。因此，我们可以使用RMQ， 因此， LCAT(u, v) = E[RMQL(H[u], H[v])] . (别忘记，RMQ返回索引)
注意：L中的连续元素相差 1.
从RMQ转换为LCA
我们已经看到在线性时间内LCA可以转为RMQ问题，RMQ问题也可以转为LCA问题。这也说明 一般的RMQ问题可以 转化为 该问题的受限版本(连续的元素在数组中相差1)。
数组 A[0, N-1]的笛卡尔树是一个二叉树 C(A), 其根是数组A的最小元素的索引。根的左孩子是 A[0, i-1]笛卡尔树 如果 i>0, 否则没有左孩子。根的右孩子是 A[i+1, N-1]的笛卡尔树。 注意，如果数组A中含有相同的元素，笛卡尔树 不一定是唯一的。 在本教程中，我们使用最小值的第一次出现，因此笛卡尔树是唯一的。可以很容易的证明 RMQA(i, j)=LCAC(i, j). 例如，
现在，我们仅需要在线性时间内计算C(A)，我们可以使用栈来实现。
开始时，栈是空的，我们将A的元素入栈。在第 i-th 步， A[i]将被放到栈中小于等于A[i]的元素中的最后一个元素的后面，所有比A[i]大的元素都被移除。在插入前，栈中元素A[i]成为 i 的左孩子，A[i]成为小于A[i]且在A[i]后面的元素的右孩子 。在每一步，栈中的第一个元素都是笛卡尔树的根，如果用栈存储元素的索引，我们很容易建立笛卡尔树。
例子，
注意，数组A中的所有元素仅入栈一次，最多被移除一次，因此时间复杂度O(N).
代码如下：
void computeTree(int A[MAXN], int N, int T[MAXN]) {
int st[MAXN], i, k, top = -1;
//we start with an empty stack
//at step i we insert A[i] in the stack
for (i = 0; i < N; i++)
{
//compute the position of the first element that is
//equal or smaller than A[i]
k = top;
while (k >= 0 && A[st[k]] > A[i])
k--;
//we modify the tree as explained above
if (k != -1)
T[i] = st[k];
if (k < top)
T[st[k + 1]] = i;
//we insert A[i] in the stack and remove
//any bigger elements
st[++k] = i;
top = k;
}
//the first element in the stack is the root of
//the tree, so it has no father
T[st[0]] = -1;
}
一个 <O(N), O(1)>复杂度的算法用于受限的RMQ问题
[说实在，没弄懂该小节!]
我们知道，使用LCA，我们可以将一般的RMQ问题转换为受限的RMQ问题（数组中的连续元素的相差 1）。我们可以利用该信息给出一个 <O(N), O(1)>时间复杂度的算法。
现在我们开始解决受限版本的RMQ问题。
数组 A[0, N-1], 其中 | A[i]-A[i+1] | = 1, i = [1, N-1]
我们将A转换为具有N-1个元素的二值数组，其中 B[i] = A[i] - A[i+1], A[i]=1 或者-1.
因此，原数组中A[i] = sum{ A[1],...,A[i]} + A[0]. 但从现在开始，我们不需要 A[0].
令 A=B
我们将A分成大小 l=[log(N) / 2] 的块，令 A'[i] 是A中第 i 个块的最小值，B[i]记录A中最小值的位置。 A和B的长度都是 N/l 长。 现在，我们使用 ST算法预处理 A' 数组， 这消耗 O(N/l * log(N/l)) = O(N)的时间和内存。
在预处理后，我们可以在O(1)时间内，在这几个块上执行查询。
我们现在展示如何执行块内的查询。注意，每个块的长度 l =[(log(N)) /2]，这是非常小的。又， A是二值数组，长度为 l 的二值子数组共有 2l=sqrt(N)个。因此，对于每个长度为 l 的二值块，我们需要在二维数组 P中查找索引对之间的RMQ值。这些需要消耗 O(sqrt(N) x l2)=O(N)的时间和空间。
为了索引二维数组P，预处理数组A中每个块的类型，并用数组 T[1, N/l]存储。块的类型是一个二值数，通过用0替换-1，1替换+1，得到。【？？？】
现在，为了计算 RMQA(i, j)分成两种情况：
- i 和 j 在同一个块中，因此我们可以使用 在P和T中计算出来的值。
- i 和 j 在不同的块中，因此我们计算三个值： 使用P和T计算从 i 到 i的末尾 的最小值，i 和 j的块之间的最小值 使用 A' 上预计算的查询，计算从 j所在的块的开始到 j
的最小值
翻译来源
Range minimum query and lowest common ancestor
