第一節(jié)?RMQ、LCA概述

? ? ? LCA:Lowest?Common?Ancestor，譯為最近公共祖先。其解釋就是說：在有根樹中，找出樹中任意兩個(gè)節(jié)點(diǎn)最近的公共祖先，或者說找到任意兩個(gè)節(jié)點(diǎn)離樹根最遠(yuǎn)的公共祖先。

? ? ? ?RMQ：Range?Minimum?Query，譯為區(qū)間最小值查詢。其解釋就是說：對(duì)于含有N個(gè)元素的數(shù)列A，在數(shù)列中找到兩個(gè)指定索引之間的最小值及最小值的位置。

第二節(jié)?RMQ Algorithm

? ?首先我們來看RQM算法，我將會(huì)根據(jù)預(yù)處理和查詢的速度介紹幾種解決該問題的方法。
? 設(shè)有數(shù)組A[N]，其表示如下：

?要求求得區(qū)間(2,7)的最小元素，如下圖所示：

解法一：Sparse?Table(ST)?algorithm
? ? ?ST算法是一種比較高效的在線處理RMQ問題的算法，所謂在線算法，是指每輸入一個(gè)查詢就會(huì)馬上處理這個(gè)查詢。ST算法首先會(huì)對(duì)序列做預(yù)處理，完成之后就可以對(duì)查詢做回答了。
? ? 分析：
? ? ? ? ? ? 預(yù)處理：O(N * LogN)。
? ? ? ? ? ? 查詢：O(1)，這樣的查詢正是我們想要的。
? 算法流程：
預(yù)處理：首先用維護(hù)一個(gè)數(shù)組M[N][LogN]，M[i][j]的值是從原序列A的i位置開始，連續(xù)2j?個(gè)元素的最小值的下標(biāo)，如下所示：

? ? ? ? ? ?

?那么，我們?nèi)绾斡?jì)算M[i][j]呢？
? ??我們采用DP的思想將區(qū)間分成兩部分，即M[i][j?-?1]和M[i][2^(j?-?1)]?，F(xiàn)在我們只需比較這兩個(gè)子區(qū)間就可以得到M[i][j]了。比較規(guī)則如下：

? ? ? ? ? ? ? ? ? ? ?

?于是乎，就可按照此寫出代碼：

void Proprocessing(int M[N][logN], int *A, int N){int i, j;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))][i - 1]]){M[i][j] = M[i][j - 1];}else{M[i][j] = A[ M[i + (1 << (j - 1))][i - 1]];}}} }

?????
https://blog.csdn.net/fengchaokobe/article/details/8104784#
??? ? ?https://blog.csdn.net/blaze003003/article/details/81084954

總結(jié)

以上是生活随笔為你收集整理的RMQ LCA的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。