LCA和RMQ的詳細討論(?!)

又開始學新的東西，突然發現我了解的東西實在很少阿

今天要講的有LCA和RMQ（兩個關係匪淺的好玩有趣酷炫東西）

講完這個希望可以進入新的一個境界，並進入可怕的『字串』

=============================================入正文

LCA有兩種簡單的作法：

第一種：


我最常用的方法，就是用二分搜的方式。先以 O(nlgn) 做出parent[k][u]，代表 u 往上2^k所到達的點，作法的精隨：parent[k+1][u] = parent[k][parent[k][u]]。接著，對於每個詢問O( lgn )，先讓兩個人的深度相同，再慢慢往上移但不要讓兩人的點相同（這個寫(想)法很酷，是iwi想到的，詳情可以看他的『邏輯腦』）。u, v 是所要詢問的兩點（假設兩點以再同一高度，若不同可以用十進位轉二進位的方法如法炮製），最後回傳的為他們的LCA。 

for( int k = MAX ; k >= 0 ; k-- ) if( parent[k][v] != parent[k][u] ) u = parent[k][v], v = parent[k][u];


return parent[0][u]; //最後還要再往上爬一格才行（超酷><）


第二種：

這才是今天的重點，把它壓扁成一條線，做RMQ！想把樹壓成一條線，唯一作法：時間戳記。但今天要的可能出現在從 u 走到 v 之間的任意點，所以在一個點被邊『走到』都要記錄他的時間戳記，因為在他們的時間戳記之間的所有點的 lev 一定<= 他們的LCA。（若有人 > 他們的LCA，則代表 u 必須走超出他們LCA再走下來才會碰到 v，這樣LCA就不是他們的LCA了，矛盾）所以對於每一個詢問，用RMQ求出之間的最小值即為所求。

==============================================進入RMQ

首先，最基本的RMQ大家都熟到炸開了吧？！也就是所謂的線段樹解法，有點太老梗了在此便不多提。我想要說一下Sparse Table（稀疏的桌子）解法，簡稱ST算法。

//////////////////////////////////////////////////////////////////////////

ST算法：O(nlgn) - O(1)，先建立一個表，tbl[x][k]，代表a[i] { i = x ~ x+2^k-1 } 的最小值，而這個算法的精隨為：tbl[x][k] = tbl[x][k-1]+tbl[x+2^(k-1)][k-1] ，簡單精巧又快速的好方法。

/////////////////////////////////////////////////////////////////////////

+-1 RMQ 算法：O(n) - O(1)，概念：塊狀分解（設c個一塊，共n個）

預處理：對n/c塊做ST -> O( (n/c) * lg(n/c) );
                對所有零碎的可能狀況建表 -> O( 2^c*c^2 ); （你知道只會有2^c種，因為相鄰的接只差一）

詢問：用 ST＋已有的零碎 -> O(1)

經過一番計算，可以發現 c = lgn/2時，預處理時間可以壓到O(n)

//////////////////////////////////////////////////////////////////////////

笛卡爾樹：（一個可以把序列轉換成樹的方式）

Definition: 根為此序列的min值，左子樹由min點左邊的序列所構成，右子樹則是右邊的。

Construction:

void 把一個節點放入一顆笛卡爾樹( int a[i], int root_id ){
       if( 其比此樹的根值大) 把一個節點放入一棵笛卡爾樹( a[i],  root_id*2+1 );
       else 把此樹拔掉，已此點取代後，在把被拔掉的樹當成此點的左子樹;
}

Property: 當要找出某區段L~R的RMQ，即為在此樹上二節點LCA的值。
（原因：LCA的性質便是 l 節點在他的左子樹，而 r 節點在他的右子樹（一般特性），且其為一個包含 l 和 r 的區段中的min（笛卡爾樹），故其為l~r區段中的min值。）


//////////////////////////////////////////////////////////////////////////

有了上述的基礎後－

當你碰上了RMQ，你可以先轉為笛卡爾樹求LCA，再轉回+-1RMQ，以 O(n) - O(1) 解決。