天天看點
傳回

ST表&LCA&RMQSparseTable

SparseTable

RMQ問題

RMQ (Range Minimum/Maximum Query)問題是指：對于長度為n的數列A，回答若幹詢問RMQ(A,i,j)(i,j<=n)，傳回數列A中下标在i,j裡的最小(大）值，也就是說，RMQ問題是指求區間最值的問題。

算法

  • 樸素（即搜尋），

    O(n)-O(qn)

     online。
  • 線段樹，

    O(n)-O(qlogn)

     online。(這個稍後補充)
  • ST（實質是動态規劃），

    O(nlogn)-O(q)

     online。ST算法（

    Sparse Table

     ），以求最大值為例，設

    d[i,j]

     表示

    [i,i+2^j-1]

     這個區間内的最大值，那麼在詢問到[a,b]區間的最大值時答案就是

    max(d[a,k], d[b-2^k+1,k])

     ，其中k是滿足

    2^k<=b-a+1

     (即長度)的最大的k,即

    k=[ln(b-a+1)/ln(2)]

     。d的求法可以用動态規劃，

    d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])

     。
  • RMQ标準算法：先規約成LCA（

    Lowest Common Ancestor

     ），再規約成限制RMQ，

    O(n)-O(q)

     online。

ST 算法

動态規劃:

我們定義狀态如下:

dp[i][j]

表示

[i,i+2^j-1]

區間内的最大值

定義狀态轉移方程如下:

dp[i][j] = max(dp[i][j-1],dp[i + 1<<(j-1)][j-1])

即将長度為

2^j

的區間拆分成兩個長度為

2^(j-1)

的區間,長區間的最大值也正是兩個短區間内的最大值中的較大者.

初始化 

// 與上文說的一樣
int dpmax[50000+100][20];
int dpmin[50000+100][20];
int a[50000+100];
void rmq_init(){
    for(int i=1;i<=n;++i){ // 針對區間長度為1情況的預處理
        dpmax[i][0]=dpmin[i][0]=a[i]; 
    }
    for(int j=1;(1<<j)<=n;++j){ // 複雜度 O(nlogn)
        for(int i=1;i+(1<<j)-1<=n;++i){
            dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
            dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
        }
    }
}

查詢

查詢的話,直接查表即可,但是由于查詢的區間可能不是二的幂次,是以需要先求

k = ceil(log(r-l+1))

,即選取區間長度

myLen = 2^k

,顯然

myLen

一定為二的幂次,并且一定不小于

(r-l+1)/2

,也就是說,如果我們以左端點為起點,選取一個長為myLen的區間,再以右端點為終點,選取一個長度為myLen的區間,這兩個區間一定能覆寫查詢區間.

// POJ 3264
int rmq_q(int l,int r){
    int k=0;
    int len=r-l+1;
    while((1<<(k+1))<=len){
            ++k;
    }
    int ans1 = max(dpmax[l][k],dpmax[r-(1<<k)+1][k]); // 區間最大值
    int ans2 = min(dpmin[l][k],dpmin[r-(1<<k)+1][k]); // 區間最小值
    return ans1-ans2;
}

LCA 問題(最近公共祖先)

介紹

對于有根樹T的兩個結點u、v，最近公共祖先LCA(T,u,v)表示一個結點x，滿足x是u、v的祖先且x的深度盡可能大。

另一種了解方式是把T了解為一個無向無環圖，而LCA(T,u,v)即u到v的最短路上深度最小的點。

LCA 問題有兩種解法,一種是線上算法,轉RMQ,然後用ST算法求解,預處理複雜度O(nlogn),單次查詢O(1);另一種是tarjan離線算法,複雜度是O(n).在此我們先隻介紹轉RMQ算法的方式.

思路

我們發現了一個最近公共祖先的性質:如果對于有根樹從根節點開始深度優先周遊,而且把經過的節點(無論曾經是否經過過),都記錄下來寫入vs[]數組,記u第一次在vs中出現的位置是p,v第一次在vs中出現的位置是q,那麼LCA(u,v)就一定是vs[]數組在[p,q]區間(假設p>q,否則反過來)内的深度最小的點! 而vs[]數組的大小顯然應該是O(n)級别的,因為一個節點最多經過兩次(葉子節點隻經過一次),是以我們用ST 以O(nlogn)的複雜度,維護一下vs[]數組,就可以在O(1)時間内應對LCA的查詢了.

洛谷p3379 

// 洛谷p3379
// 目前此寫法(scanf,printf,手寫鄰接表)能在不開O2優化下通過洛谷p3379
// 還有帶權LCA,也是也可以用這種方法計算,而且(應該是)和樹的根無關,參考poj 1986  和 hdu 2586
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000100
#define pb push_back
int vs[MAXN<<1]; // 存儲歐拉序,大概是原序列的2倍長度
int depth[MAXN<<1]; // 和vs數組中的元素一一對應,表示他們的深度(即使一個節點多次加入vs,其depth[]對應的都是同一個值,)
int id[MAXN]; // 可以了解為反向映射,id[u]傳回節點u在vs數組中第一次出現的下标
// log(1e5) < 20
int dp[MAXN<<1][20];
int head[MAXN],nxt[MAXN],to[MAXN]; // 鄰接表,此題寫vector會逾時
vector<int> v[MAXN];
int dfsCnt=0;
int n,m,q,root;
int cnt=0;
void addEdge(int x,int y) {
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}

void dfs(int u,int fa,int dep) { // 建構vs,depth,id數組,以備之後查詢使用,看似複雜,實則總共時間複雜度為O(n)
    id[u]=dfsCnt; // 僅在第一次通路節點時更新
    vs[dfsCnt]=u;
    depth[dfsCnt]=dep;
    ++dfsCnt;
    for(int i=head[u]; i!=-1; i=nxt[i]) {
        int v = to[i];
        if(v==fa) // 樹上無環,隻要不走回頭路不可能出現無限遞歸
            continue;
        dfs(v,u,dep+1);
        vs[dfsCnt]=u; // 回溯,将目前節點再次加入vs數組
        depth[dfsCnt]=dep;
        ++dfsCnt;
    }
}
void rmq_init(int NN) {
    for(int i=0; i<=NN; ++i) {
        dp[i][0]=i;
        // 看似違反直覺,實際上就是這樣,這個i指的是vs數組的下标,同時也是dep數組的下标,則depth[] 下标在[i,i]範圍内最小的深度的節點的下标自然是i(就這一個節點嘛)
        // 重點是要了解depth數組的下标的内涵是dfs序的時間戳
    }
    for(int j=1; (1<<j)<=NN; ++j) {
        for(int i=1; i+(1<<j)-1<=NN; ++i) {
            int a = dp[i][j-1];
            int b = dp[i+(1<<(j-1))][j-1];
            if(depth[a]<=depth[b]) { // dp數組存的隻是下标,而判斷需要借助depth數組
                dp[i][j]=a;
            } else {
                dp[i][j]=b;
            }
        }
    }
}
// 此處的dp有些魔改 dp[i][j]意義實際上是 **vs數組中**,編号在[i,i+2^j-1]範圍内深度最小的元素的編号
int rmq_query(int l,int r) { // 查詢的是vs數組,切記切記
    int k = (int)(log(r-l+1)/log(2)); //  比之前的模拟法求k要快一些,近乎是O(1)
    int a = dp[l][k];
    int b = dp[r-(1<<k)+1][k];
    return depth[a]<=depth[b]?a:b;
}

int query(int u,int v) {
    int x = id[u]; // u 第一次在vs中出現的下标
    int y = id[v]; // v 第一次在vs中出現的下标
    if(x<y) {
        return vs[rmq_query(x,y)];
    } else {
        return vs[rmq_query(y,x)];
    }
}
void Build_dfs() {
    dfsCnt=1;
    memset(vs,0,sizeof(vs));
    memset(id,0,sizeof(id));
    memset(depth,0,sizeof(depth));
    dfs(root,-1,0);
    rmq_init(dfsCnt-1);
}
int main() {
    ios::sync_with_stdio(0);
    scanf("%d%d%d",&n,&q,&root);
    m=n-1;
    memset(head,-1,sizeof(head));
    for(int i=0; i<m; ++i) {
        int a,b;
        scanf("%d%d",&a,&b);
        addEdge(a,b);
        addEdge(b,a);
    }
    Build_dfs();
    for(int i=0; i<q; ++i) {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",query(a,b));
    }
    return 0;
}

HDU2586 

// HDU 2586
// 模闆題
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500100
#define pb push_back
#define ll long long
int vs[MAXN<<1];
int depth[MAXN<<1];
int id[MAXN];
int dp[MAXN<<1][20];
int head[MAXN],nxt[MAXN],to[MAXN],vis[MAXN],w[MAXN];
ll sum[MAXN]; // 用以儲存從根節點到此節點的路徑的長度之和,類似字首和的思想
int dfsCnt=0;
int n,m,q,root;
int cnt=0;
void addEdge(int x,int y,int weight) {
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    w[cnt]=weight;
    to[cnt]=y;
}

void dfs(int u,int fa,int dep) { // 建構vs,depth,id數組,以備之後查詢使用,看似複雜,實則總共時間複雜度為O(n)
    id[u]=dfsCnt; // 僅在第一次通路節點時更新
    vs[dfsCnt]=u;
    depth[dfsCnt]=dep;
    ++dfsCnt;
    for(int i=head[u]; i!=-1; i=nxt[i]) {
        int v = to[i];
        if(v==fa)
            continue;
        if(!vis[v]) {
            sum[v]=sum[u]+w[i]; // 維護字首和
            vis[v]=1;
        }
        dfs(v,u,dep+1);
        vs[dfsCnt]=u; // 回溯,将目前節點再次加入vs數組
        depth[dfsCnt]=dep;
        ++dfsCnt;
    }
}
void rmq_init(int NN) {
    for(int i=0; i<=NN; ++i) {
        dp[i][0]=i;
        // 看似違反直覺,實際上就是這樣,這個i指的是vs數組的下标,同時也是dep數組的下标,
        // 重點是要了解depth數組的下标的内涵是dfs序的時間戳
    }
    for(int j=1; (1<<j)<=NN; ++j) {
        for(int i=1; i+(1<<j)-1<=NN; ++i) {
            int a = dp[i][j-1];
            int b = dp[i+(1<<(j-1))][j-1];
            if(depth[a]<=depth[b]) {
                dp[i][j]=a;
            } else {
                dp[i][j]=b;
            }
        }
    }
}

int rmq_query(int l,int r) { 
    int k = (int)(log(r-l+1)/log(2)); 
    int a = dp[l][k];
    int b = dp[r-(1<<k)+1][k];
    return depth[a]<=depth[b]?a:b;
}

int query(int u,int v) {
    int x = id[u]; // u 第一次在vs中出現的下标
    int y = id[v]; // v 第一次在vs中出現的下标
    int lca;
    if(x<y) {
        lca =  rmq_query(x,y);
    } else {
        lca =  rmq_query(y,x);
    }
    return sum[u]+sum[v]-2*sum[vs[lca]]; // 此處這裡不是傳回lca了,而是傳回u經lca再到v的路徑長度,運用字首和的思想, u到v的距離 == 根到u的距離 + 根到v的距離 - 2*根到lca的距離
}
void Build_dfs() {
    dfsCnt=1;
    memset(vs,0,sizeof(vs));
    memset(id,0,sizeof(id));
    memset(depth,0,sizeof(depth));
    dfs(root,-1,0);
    rmq_init(dfsCnt-1);
}
int main() {
    ios::sync_with_stdio(0);
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&q);
        root=1;
        m=n-1;
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        sum[1]=0;
        vis[1]=1;
        for(int i=0; i<m; ++i) {
            int a,b,weight;
            scanf("%d%d%d",&a,&b,&weight);
            addEdge(a,b,weight);
            addEdge(b,a,weight);
        }
        Build_dfs();
        for(int i=0; i<q; ++i) {
            int a,b;
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(a,b));
        }
    }
    return 0;
}
資料結構 ACM LCA RMQ ST
上一篇: SymmetricDS配置Initial Load的步驟
下一篇: Spring Boot#AutoConfigure

繼續閱讀