長鏈剖分

一、簡介

長鏈剖分是一種基於動態規劃思想的算法，用於解決靜態區間查詢的問題。它將一條長鏈分為若干個短鏈，使得查詢的時間複雜度降至 O(log n)，解決了靜態區間查詢的效率問題。

長鏈剖分可以被用於很多靜態區間查詢的場景，比如線段樹、樹鏈剖分、主席樹等。

二、核心思想

長鏈剖分的核心思想是將一條較長的鏈分為若干個較短的鏈，使得查詢的時間複雜度降低到 O(log n)。

具體實現過程中，我們可以將一條長鏈分割成 k 條較短的鏈，每條鏈的長度為 O(log n)，並建立一個虛樹，虛樹是由長鏈上的一些重鏈、輕鏈以及一些根據 LCA（最近公共祖先）得到的節點組成的一棵樹。

每個節點都對應着一條較短的鏈，較短鏈上的信息可以預處理，查詢的時候只需要暴力查詢所有較短鏈上的信息即可。

//代碼示例
void dfs(int u, int fa, int &k) {
    size[u] = 1;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v, u, k);
        size[u] += size[v];
        if(size[v] > size[son[u]]) son[u] = v;
    }
    if(size[u] > size[son[u]] + 1) //重鏈
        c[++k] = u;
}

三、詳細實現

1、建虛樹

在實現長鏈剖分之前，需要先建立虛樹。虛樹是一棵由長鏈上的一些重鏈、輕鏈以及一些根據 LCA（最近公共祖先）得到的節點組成的一棵樹。

具體操作如下：

1）將整個鏈縮成點。將一條長鏈縮成一個點作為虛樹的根節點，則原先的長鏈上面所有的點成為虛樹上的葉子節點。

2）可以根據 LCA 算法，將每一個詢問中的區間變成一顆虛子樹，其中 LCA 到詢問兩端的點的路徑就是虛子樹上的重鏈，而非這些點到 LCA 的路徑就是輕鏈。

//代碼示例
void dfs(int u, int fa, int &k) {
    size[u] = 1;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v, u, k);
        size[u] += size[v];
        if(size[v] > size[son[u]]) son[u] = v;
   }
    if(size[u] > size[son[u]] + 1) //重鏈
        c[++k] = u;
}

void dfs2(int u, int fa, int top) {
    id[u] = ++cnt;
    tp[u] = top;
    rk[cnt] = u;
    if(son[u]) dfs2(son[u], u, top);
    for(int i = head[u]; ~i; i = e[i].nxt)
        if(e[i].to != fa && e[i].to != son[u]) dfs2(e[i].to, u, e[i].to);
}

void build(int L, int R, int rt) {
    if(L == R) {
        tr[rt].push_back(p[rk[L]]);
        return;
    }
    int mid = (L + R) >> 1;
    build(L, mid, ls(rt)); build(mid + 1, R, rs(rt));
    merge(tr[ls(rt)].begin(), tr[ls(rt)].end(), tr[rs(rt)].begin(), tr[rs(rt)].end(), back_inserter(tr[rt]));
}

2、長鏈剖分

有了虛樹之後，就可以進行長鏈剖分了。可以按照以下步驟進行：

1）根據每個節點的子樹大小，判斷重兒子重鏈，輕兒子輕鏈。

2）每次查詢的時候從查詢區間兩個端點向上走，直到走到同一條鏈上，查詢沿途鏈上的信息。

代碼實現如下：

//代碼示例
struct node {
    int l, r;
    LL sum;
    node() {}
    node(int l, int r, LL sum): l(l), r(r), sum(sum) {}
};

vectorT[maxn << 2];

void query(int x, int y, int Lim, int u, int fa, vector &v) {
    if(x > y || x > Lim) return;
    if(y  id[y]) swap(x, y);
        auto it1 = lower_bound(T[u].begin(), T[u].end(), node(id[x], -1, -1));
        auto it2 = upper_bound(T[u].begin(), T[u].end(), node(id[y], -1, -1));
        for(auto it = it1; it != it2; it++) v.push_back(*it);
        return;
    }
    if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
    auto it1 = lower_bound(T[u].begin(), T[u].end(), node(id[tp[x]], -1, -1));
    auto it2 = upper_bound(T[u].begin(), T[u].end(), node(id[x], -1, -1));
    for(auto it = it1; it != it2; it++) v.push_back(*it);
    query(fa, fa, Lim, u, fa, v);
}

四、優化

在實際應用過程中，有若干優化方法可以減小長鏈剖分的常數和複雜度，包括但不限於：

1）將長鏈剖分和主席樹結合使用，可以進一步優化空間；

2）對於一些複雜的邊權計算場景，可以先對邊權進行預處理，以減小邊權計算的複雜度；

3）使用同餘定理等其他技巧來加速。

五、總結

長鏈剖分是一種重要的靜態區間查詢算法，可以有效地提高查詢效率。通過對長鏈剖分的實現及優化，我們可以更加高效地解決一些靜態區間查詢的問題。