介紹
從一個(gè)有根樹中尋找一對(duì)節(jié)點(diǎn)的最小公共祖先(Lowest common ancestor)的問題，從20世紀(jì)就已經(jīng)被充分研究了闽撤，現(xiàn)在已經(jīng)成為了圖論中的基本算法添吗。這個(gè)問題之所以有趣届惋，不僅是因?yàn)榻鉀Q算法非常有技巧性，還因?yàn)樵撍惴ū粡V泛的應(yīng)用于字符串處理和計(jì)算生物學(xué)上奄薇，例如驳阎，LCA可以使用后綴樹或其他樹結(jié)構(gòu)解決。Harel and Tarjan第一次研究該問題馁蒂，他們向我們展示通過用線性時(shí)間去處理輸入樹步淹，每次查詢只需要常量時(shí)間遥倦。他們的工作已經(jīng)被后人擴(kuò)展了，本教程將為讀者展示許多可以用于其他問題的有趣算法。
RMQ算法以數(shù)組作為底層數(shù)據(jù)結(jié)構(gòu)压真，在特定的區(qū)間中场勤，發(fā)現(xiàn)具有最小元素的位置鹰椒。再文章后面，我們將會(huì)看到LCA問題可以轉(zhuǎn)化為RMQ問題的受限版本(與generalized相對(duì))劫瞳。RMQ不僅可以用于LCA，還可以用于字符串預(yù)處理绷柒，字符串預(yù)處理使用后綴數(shù)組(一個(gè)新的支持字符串查詢的數(shù)據(jù)結(jié)構(gòu)志于，可以替代后綴樹，但會(huì)使用更少的內(nèi)存废睦，且容易編程實(shí)現(xiàn))
本教程伺绽，將先介紹RMQ。我們將先介紹一些效率不高嗜湃，但容易編程實(shí)現(xiàn)的方法奈应，來解決RMQ問題。然后介紹LCA和RMQ之間的關(guān)系购披，我們將先回顧兩個(gè)解決LCA問題的簡單方法杖挣，然后說明RMQ等價(jià)于LCA問題。最后刚陡，我們將會(huì)看到RMQ問題如何轉(zhuǎn)化為它的受限版本惩妇，以及用于受限版本的快速算法。
記號(hào)
算法的預(yù)處理時(shí)間記為f(n)筐乳， 查詢時(shí)間記做g(n). 算法的整體復(fù)雜度記做<f(n), g(n)>
在某個(gè)數(shù)組A上歌殃，位于區(qū)間i和j之間的最小值的位置記做 RMQA(i, j)
在有根節(jié)點(diǎn)樹T上，距離根節(jié)點(diǎn)最遠(yuǎn)的且是節(jié)點(diǎn)u和v的共同祖先的節(jié)點(diǎn) 記做 LCAT(u, v)
Range Minimum Query(RMQ)
給定數(shù)組A[1, N-1], 尋找在給定區(qū)間上最小元素的位置蝙云。
RMQ的平凡算法
使用二維數(shù)組M[0, N-1][0, N-1]存儲(chǔ)區(qū)間[i, j]的RMQA(i, j)值.
顯然平凡算法的時(shí)間復(fù)雜度<O(N3, O(1))>氓皱。然而我們可以使用動(dòng)態(tài)規(guī)劃的方法將復(fù)雜度減少到<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;
}
一個(gè)<O(N), O(sqrt(N))>方法
思路是將數(shù)組A分成sqrt(N)的部分，然后使用數(shù)組M[0, sqrt(N)-1]存儲(chǔ)這些部分的最小值 （見下圖）贮懈。顯然匀泊，只需要掃描一遍數(shù)組A，就可以完成預(yù)處理朵你。但查詢，要稍微花費(fèi)點(diǎn)力氣揣非。
查詢RMQA(i, j): 思路就是從sqrt(N)個(gè)部分和與區(qū)間[i, j]交叉的區(qū)間計(jì)算出抡医。比如RMQA(2, 7), 我們需要比較 A[2], A[M[1]], A[6], A[7]的大小，然后得到最小值的位置早敬。顯然每次計(jì)算最多有3 x sqrt(N)次比較操作.
該算法的優(yōu)點(diǎn)：快速編碼忌傻，可以調(diào)整為動(dòng)態(tài)版本（在兩次查詢之間可以改變數(shù)組元素）.
稀疏表算法(Sparse Table (ST) algorithm)
預(yù)處理RMQ的更好方法就是利用動(dòng)態(tài)規(guī)劃的方法，對(duì)長度為2k的子數(shù)組預(yù)處理搞监。 我們使用數(shù)組M[0, N-1][0, Log(N)]存儲(chǔ)結(jié)果水孩，M[i][j]存儲(chǔ)從位置i開始，長度為2j的子數(shù)組中最小值的位置琐驴。例如俘种，
當(dāng)計(jì)算M[i][j], 我們必須查找 區(qū)間的前半部分最小值的位置 M[i][j-1] 和區(qū)間的后半部分的最小值的位置 M[i+2j-1-1][j-1].
預(yù)處理代碼如下:
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): 思路就是選出兩個(gè)可以覆蓋區(qū)間[i,j]的塊秤标，找出其中最小的。令 k = [log(j-i+1)]
時(shí)間復(fù)雜度<O(Nlog(N), O(1))>
區(qū)間樹
RMQ問題也可是使用區(qū)間數(shù)解決宙刘，區(qū)間數(shù)是一個(gè)堆狀的數(shù)據(jù)結(jié)構(gòu)苍姜，可以用log時(shí)間上執(zhí)行快速更新和查詢操作，我們用遞推的方式定義位于區(qū)間[i, j]的區(qū)間樹如下:
- 第一個(gè)節(jié)點(diǎn)存放區(qū)間[i,j ]的信息悬包。
- 如果 i < j, 左右孩子分別存放區(qū)間[i, (i+j)/2]和[(i+j)/2+1, j]的信息衙猪。
例如
使用區(qū)間樹解決RMQ問題，我們需要使用數(shù)組 M[1, 2 x 2[logN]+1]存儲(chǔ)區(qū)間樹的信息布近，M[i]表示區(qū)間樹第i個(gè)節(jié)點(diǎn)的最小值的索引信息垫释。
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];
}
}
查詢區(qū)間[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;
}
我們應(yīng)該使用參數(shù)為 node=1, b=0, e=N-1調(diào)用該函數(shù)，因?yàn)榈谝粋€(gè)節(jié)點(diǎn)覆蓋的區(qū)間是[0, N-1]撑瞧。
時(shí)間復(fù)雜度: <O(N), O(logN)>
區(qū)間樹優(yōu)點(diǎn)：靈活的數(shù)據(jù)結(jié)構(gòu)饶号，可以用于RMQ問題的動(dòng)態(tài)版本，在區(qū)間搜索問題也有很多廣泛的應(yīng)用季蚂。
最小公共祖先(Lowest Common Ancestor, LCA)
一個(gè) <O<N>, O(sqrt(N))>算法
在RMQ問題中茫船，我們將數(shù)組區(qū)間分成相等的幾個(gè)部分，在LCA問題中也可以這樣做扭屁。
具體的算谈，我們將樹分成sqrt(H)個(gè)部分，H表示樹的高度料滥。因此然眼，第一個(gè)部分包含的層次在0和sqrt(H)-1之間，第二個(gè)部分包含的層次在sqrt(H)和2*sqrt(H)-1之間葵腹。例如高每，
對(duì)每個(gè)節(jié)點(diǎn)node，我們知道其祖先位于節(jié)點(diǎn)node所在部分的上一個(gè)部分的最后一層. 我們將會(huì)預(yù)處理践宴，并將信息放在數(shù)組P[1, MAXN]中鲸匿。例如，
位于第一個(gè)部分的節(jié)點(diǎn)標(biāo)記為1阻肩，P[i]=1.
可以看到带欢，位于部分第一層的節(jié)點(diǎn) 都有 P[i]=T[i], 我們可以使用深度搜索預(yù)處理數(shù)組P( T[i]是節(jié)點(diǎn)i的父親， nr 是 [sqrt(H)], L[i]節(jié)點(diǎn)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烤惊，先尋找找到所在部分乔煞，然后在計(jì)算
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;
}
該函數(shù)至多需要 2 x sqrt(H)個(gè)操作，因此我們的時(shí)間復(fù)雜度 <O(N), O(sqrt(H))>, 其中 H 是樹的高度柒室，最壞情況是當(dāng)H==N時(shí)渡贾。
算法的優(yōu)點(diǎn)：編碼簡單，快速雄右。
時(shí)間復(fù)雜度<O(NlogN), O(LogN)>的算法
我們可以使用動(dòng)態(tài)規(guī)劃解決問題空骚。 我們用二維數(shù)組 P[1, N][1, LogN]存儲(chǔ)相關(guān)信息纺讲，P[i][j]表示i的第 2j-th祖先。我們使用下面的遞推公式府怯。
預(yù)處理算法如下刻诊，
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];
}
時(shí)空復(fù)雜度：O(NlogN)
查詢算法，
令 L[i] 表示節(jié)點(diǎn)i的層
如果節(jié)點(diǎn) p 和 q 位于同一層牺丙，那么我們可以使用元二分查找計(jì)算 LCA(p, q)则涯。
因此，如果 P[p][i] != P[q][i], 那么LCA(p, q)位于更高的層上冲簿，我們需要計(jì)算 LCA(p=P[p][i], q = P[q][i]), 其中 i 在 log(L[p])和0之間粟判，最后，p和q將具有相同的父親峦剔，返回T[p].
如果 p 和 q 不在同一層档礁，不失一般性，假設(shè) 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];
}
可以看到該函數(shù)最多運(yùn)行 2 x Log(H)次操作，其中H是樹的高度惨险，最壞情況下發(fā)生在H=N的時(shí)候
將LCA問題變?yōu)镽MQ問題
線性時(shí)間內(nèi)羹幸，將LCA轉(zhuǎn)為RMQ問題，因此任何用于RMQ的都可以用于LCA問題辫愉。我們使用下圖栅受，展示如何將LCA轉(zhuǎn)換為RMQ問題。
注意到恭朗，LCAT(u, v)是在深度優(yōu)先搜索中節(jié)點(diǎn)u和v的過程中屏镊，相遇的節(jié)點(diǎn)中的距離根節(jié)點(diǎn)最近的節(jié)點(diǎn)。
因此痰腮，在樹的歐拉路徑中而芥，我們可以考慮位于節(jié)點(diǎn)u和v的索引之間的所有節(jié)點(diǎn)，然后查找其中處于最低層的節(jié)點(diǎn)诽嘉。為了做到這點(diǎn)蔚出，我們需要三個(gè)數(shù)組：
- E[1, 2 x N-1] - 樹的歐拉路徑上的訪問過的節(jié)點(diǎn)； E[i] 路徑中第 i 個(gè)訪問過的節(jié)點(diǎn)虫腋。
- L[1, 2 x N-1] - 樹的歐拉路徑上訪問過的節(jié)點(diǎn)在樹中的層次；L[i] 節(jié)點(diǎn) E[i] 的層次稀余。（第 i 個(gè)訪問的節(jié)點(diǎn)的層次）
- H[1, N] - H[i] 是在 E 中第一次遇到節(jié)點(diǎn) i 的索引（記錄節(jié)點(diǎn) i 第幾次出現(xiàn)都可以悦冀，如果只記錄第一次出現(xiàn)的，也沒什么問題）
假設(shè) H[u] < H[v] (否則睛琳，就交換 u 和 v)盒蟆。 顯然踏烙，可以看到在 節(jié)點(diǎn)u和v第一次出現(xiàn)的區(qū)間之間的節(jié)點(diǎn) 是 E[H[u]...H[v]]. 現(xiàn)在，我們必須查找這些節(jié)點(diǎn)中處于最低層次的節(jié)點(diǎn)历等。因此讨惩，我們可以使用RMQ， 因此寒屯， LCAT(u, v) = E[RMQL(H[u], H[v])] . (別忘記荐捻，RMQ返回索引)
注意：L中的連續(xù)元素相差 1.
從RMQ轉(zhuǎn)換為LCA
我們已經(jīng)看到在線性時(shí)間內(nèi)LCA可以轉(zhuǎn)為RMQ問題，RMQ問題也可以轉(zhuǎn)為LCA問題寡夹。這也說明 一般的RMQ問題可以 轉(zhuǎn)化為 該問題的受限版本(連續(xù)的元素在數(shù)組中相差1)处面。
數(shù)組 A[0, N-1]的笛卡爾樹是一個(gè)二叉樹 C(A), 其根是數(shù)組A的最小元素的索引。根的左孩子是 A[0, i-1]笛卡爾樹 如果 i>0, 否則沒有左孩子菩掏。根的右孩子是 A[i+1, N-1]的笛卡爾樹魂角。 注意，如果數(shù)組A中含有相同的元素智绸，笛卡爾樹 不一定是唯一的野揪。 在本教程中，我們使用最小值的第一次出現(xiàn)瞧栗，因此笛卡爾樹是唯一的斯稳。可以很容易的證明 RMQA(i, j)=LCAC(i, j). 例如沼溜，
現(xiàn)在平挑，我們僅需要在線性時(shí)間內(nèi)計(jì)算C(A)，我們可以使用棧來實(shí)現(xiàn)系草。
開始時(shí)通熄，棧是空的，我們將A的元素入棧找都。在第 i-th 步唇辨， A[i]將被放到棧中小于等于A[i]的元素中的最后一個(gè)元素的后面，所有比A[i]大的元素都被移除能耻。在插入前赏枚，棧中元素A[i]成為 i 的左孩子，A[i]成為小于A[i]且在A[i]后面的元素的右孩子 晓猛。在每一步饿幅，棧中的第一個(gè)元素都是笛卡爾樹的根，如果用棧存儲(chǔ)元素的索引戒职，我們很容易建立笛卡爾樹栗恩。
例子，
注意洪燥，數(shù)組A中的所有元素僅入棧一次磕秤，最多被移除一次乳乌，因此時(shí)間復(fù)雜度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;
}
一個(gè) <O(N), O(1)>復(fù)雜度的算法用于受限的RMQ問題
[說實(shí)在，沒弄懂該小節(jié)!]
我們知道市咆，使用LCA汉操，我們可以將一般的RMQ問題轉(zhuǎn)換為受限的RMQ問題（數(shù)組中的連續(xù)元素的相差 1）。我們可以利用該信息給出一個(gè) <O(N), O(1)>時(shí)間復(fù)雜度的算法蒙兰。
現(xiàn)在我們開始解決受限版本的RMQ問題磷瘤。
數(shù)組 A[0, N-1], 其中 | A[i]-A[i+1] | = 1, i = [1, N-1]
我們將A轉(zhuǎn)換為具有N-1個(gè)元素的二值數(shù)組，其中 B[i] = A[i] - A[i+1], A[i]=1 或者-1.
因此癞己，原數(shù)組中A[i] = sum{ A[1],...,A[i]} + A[0]. 但從現(xiàn)在開始膀斋，我們不需要 A[0].
令 A=B
我們將A分成大小 l=[log(N) / 2] 的塊，令 A'[i] 是A中第 i 個(gè)塊的最小值痹雅，B[i]記錄A中最小值的位置仰担。 A和B的長度都是 N/l 長。 現(xiàn)在绩社，我們使用 ST算法預(yù)處理 A' 數(shù)組摔蓝， 這消耗 O(N/l * log(N/l)) = O(N)的時(shí)間和內(nèi)存。
在預(yù)處理后愉耙，我們可以在O(1)時(shí)間內(nèi)贮尉，在這幾個(gè)塊上執(zhí)行查詢。
我們現(xiàn)在展示如何執(zhí)行塊內(nèi)的查詢朴沿。注意猜谚，每個(gè)塊的長度 l =[(log(N)) /2]，這是非常小的赌渣。又魏铅， A是二值數(shù)組，長度為 l 的二值子數(shù)組共有 2l=sqrt(N)個(gè)坚芜。因此览芳，對(duì)于每個(gè)長度為 l 的二值塊，我們需要在二維數(shù)組 P中查找索引對(duì)之間的RMQ值鸿竖。這些需要消耗 O(sqrt(N) x l2)=O(N)的時(shí)間和空間沧竟。
為了索引二維數(shù)組P，預(yù)處理數(shù)組A中每個(gè)塊的類型缚忧，并用數(shù)組 T[1, N/l]存儲(chǔ)悟泵。塊的類型是一個(gè)二值數(shù)，通過用0替換-1闪水，1替換+1魁袜，得到《氐冢【峰弹？？芜果？】
現(xiàn)在鞠呈，為了計(jì)算 RMQA(i, j)分成兩種情況：
- i 和 j 在同一個(gè)塊中，因此我們可以使用 在P和T中計(jì)算出來的值右钾。
- i 和 j 在不同的塊中蚁吝，因此我們計(jì)算三個(gè)值： 使用P和T計(jì)算從 i 到 i的末尾 的最小值，i 和 j的塊之間的最小值 使用 A' 上預(yù)計(jì)算的查詢舀射，計(jì)算從 j所在的塊的開始到 j
的最小值
翻譯來源
Range minimum query and lowest common ancestor
