不忘初心
时刻前行

树链剖分的思想

树链剖分是一种思想,而不是一种具体的实现方式

当要维护树上的某些信息时,将树剖成若干条链,再利用区间数据结构去进行维护,可以极大的降低维护难度,提高维护效率,而这个思想就是树链剖分

树链剖分的实现

为了实现这个思想,我们需要找到一种剖分的规则,且能使维护效率提高

具体的来说,在剖分后,要尽量的使两点之间的路径经过的链的条数尽量的小,每一条链都可以用序列上的数据结构来维护

长链剖分

一个较为容易想到的思路是,将一个点向他所有儿子中,深度最深的点连一条长边,向其他的点连一条短边

所有长边就组合出了若干条长链

长链剖分的部分性质:

  • 任意点只属于一条长链

  • 任意点的祖先所在长链的长度一定大于等于该点

  • 任意长链上的 dfs 序一定是连续的

  • 任意点到根经过的短边最多 \sqrt{n}

但很容易就能构造出卡长链剖分的树

长链剖分被广泛的用于求任意点的 k 极祖先,维护与深度有关的信息

以求 LCA 为例,下面是长链剖分的代码

struct node { int fa, len, hv, top, dep; } p[maxn];
void dfs(int u) {
    p[u].dep = p[p[u].fa].dep + 1, p[u].len = p[u].dep;
    int maxson = -1;
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v != p[u].fa) {
            p[v].fa = u, dfs(v), p[u].len = max(p[u].len, p[v].len);
            if (p[v].len > maxson) {
                p[u].hv = v, maxson = p[v].len;
            }
        }
    }
}
void dfs2(int u, int topval) {
    p[u].top = topval;
    if (p[u].hv) dfs2(p[u].hv, topval);
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v != p[u].fa && v != p[u].hv) dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (1) {
        if (p[u].top == p[v].top) return p[u].dep < p[v].dep ? u : v;
        if (p[p[u].top].dep >= p[p[v].top].dep) swap(u, v);
        v = p[p[v].top].fa;
    }
}

重链剖分

重链剖分是指,将一个点向他所有儿子中,子树大小最大的点连一条重边,向其他的点连一条轻边

所有重边就组合出了若干条重链

重链剖分的部分性质:

  • 任意点只属于一条重链

  • 重链上的点, $dfs 序是连续的

  • 任意点到根经过的轻边最多 \log n

以求 LCA 为例,下面是重链剖分的代码

struct node { int fa, sz, hv, top, dep; } p[maxn];
void dfs(int u) {
    p[u].dep = p[p[u].fa].dep + 1, p[u].sz = 1;
    int maxson = -1;
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v != p[u].fa) {
            p[v].fa = u, dfs(v), p[u].sz += p[v].sz;
            if (p[v].sz > maxson) {
                p[u].hv = v, maxson = p[v].sz;
            }
        }
    }
}
void dfs2(int u, int topval) {
    p[u].top = topval;
    if (p[u].hv) dfs2(p[u].hv, topval);
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v != p[u].fa && v != p[u].hv) dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (1) {
        if (p[u].top == p[v].top) return p[u].dep < p[v].dep ? u : v;
        if (p[p[u].top].dep >= p[p[v].top].dep) swap(u, v);
        v = p[p[v].top].fa;
    }
}

对比

重链剖分更常用,因为他的复杂度更稳定

而长链剖分近在特殊问题时使用

仅 LCA 而言,长链剖分比重链剖分要慢 0.2s 左右

应用

无论是哪种剖分的方式,如果我们在第二次 dfs 中记录 dfs 序,那么我们可以发现,一条重/长链上的点 dfs 序都是连续的

于是我们只需要维护他们的 dfs 序即可

修改操作:

function change(x, y, val):
    while top[x] ≠ top[y] do
        if dep[top[x]] < dep[top[y]] then
            swap(x, y)
        data_structure_change(dfn[top[x]], dfn[x], val)
        x := fa[top[x]];
    if dfn[x] > dfn[y] then
        swap(x, y)
    data_structure_change(dfn[x], dfn[y], val);

查询操作:

function query(x, y):
    while top[x] ≠ top[y] do
        if dep[top[x]] < dep[top[y]] then
            swap(x, y)
        data_structure_query(dfn[top[x]],dfn[x], val)
        x := fa[top[x]];
    ifdfn[x] >dfn[y] then
        swap(x, y)
    data_structure_query(dfn[x],dfn[y], val);

例题

Luogu P3384【模板】树链剖分

给出一个包含 n 个节点的点带权树,支持链加,链求和,子树加,子树求和

树链剖分


注意到除了链加和链求和这两个树链剖分本就支持的操作,还有子树加与子树求和

不过我们注意到,对于 x 的子树中的所有的节点,其 dfs 序的编号都是连续的

类似维护链,也可以直接在 dfs 序上维护

时间复杂度 O(n \log^2 n)

代码

#include <bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define DEBUG(x) cerr << #x << " = " << x << endl;
using namespace std;
const int maxn = 1e5 + 10, maxm = 1e5 + 10;
int n, m, rt, mod;

int cnt, head[maxn];
struct edge { int nxt, to; } e[maxm << 1];
void add(int u, int v) { e[++cnt].to = v, e[cnt].nxt = head[u], head[u] = cnt; }

struct points { int val, dep, fa, top, sz, son, dfn; } vtx[maxn];
void dfs1(int u, int fa, int dep) {
    vtx[u].fa = fa, vtx[u].dep = dep, vtx[u].sz = 1;
    int max_size = 0;
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v == fa) continue;
        dfs1(v, u, dep + 1);
        vtx[u].sz += vtx[v].sz;
        if (vtx[v].sz > max_size) {
            max_size = vtx[v].sz, vtx[u].son = v;
        }
    }
}
int dfsclock = 0, dtp[maxn];
void dfs2(int u, int top) {
    vtx[u].dfn = ++dfsclock, vtx[u].top = top, dtp[dfsclock] = u;
    if (vtx[u].son) dfs2(vtx[u].son, top);
    for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
        if (v == vtx[u].fa || v == vtx[u].son) continue;
        dfs2(v, v);
    }
}

struct segmenttree { int sum, tag; } t[maxn << 2];
void pushup(int k) { t[k].sum = (t[ls(k)].sum % mod + t[rs(k)].sum % mod) % mod; }
void pushdown(int k, int l, int r) {
    int mid = (l + r) >> 1;
    t[ls(k)].sum += (mid - l + 1) * t[k].tag % mod, t[rs(k)].sum += (r - mid) * t[k].tag % mod;
    t[ls(k)].sum %= mod, t[rs(k)].sum %= mod;
    t[ls(k)].tag += t[k].tag, t[rs(k)].tag += t[k].tag;
    t[ls(k)].tag %= mod, t[rs(k)].tag %= mod;
    t[k].tag = 0;
}
void build(int k, int l, int r) {
    if (l == r) { t[k].sum = vtx[dtp[l]].val % mod; return ; }
    int mid = (l + r) >> 1;
    build(ls(k), l, mid), build(rs(k), mid + 1, r);
    pushup(k);
}
void modify(int k, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) { t[k].sum += (r - l + 1) * val % mod, t[k].sum %= mod, t[k].tag += val, t[k].tag % mod; return ; }
    int mid = (l + r) >> 1;
    pushdown(k, l, r);
    if (ql <= mid) modify(ls(k), l, mid, ql, qr, val);
    if (qr > mid) modify(rs(k), mid + 1, r, ql, qr, val);
    pushup(k);
}
int query(int k, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return t[k].sum;
    int mid = (l + r) >> 1, res = 0;
    pushdown(k, l, r);
    if (ql <= mid) res += query(ls(k), l, mid, ql, qr), res %= mod;
    if (qr > mid) res += query(rs(k), mid + 1, r, ql, qr), res %= mod;
    return res % mod;
}

void opt1(int u, int v, int val) {
    val %= mod;
    while (vtx[u].top != vtx[v].top) {
        if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
        modify(1, 1, n, vtx[vtx[u].top].dfn, vtx[u].dfn, val);
        u = vtx[vtx[u].top].fa;
    }
    modify(1, 1, n, min(vtx[u].dfn, vtx[v].dfn), max(vtx[u].dfn, vtx[v].dfn), val);
}
int opt2(int u, int v) {
    int ans = 0;
    while (vtx[u].top != vtx[v].top) {
        if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
        ans += query(1, 1, n, vtx[vtx[u].top].dfn, vtx[u].dfn) % mod, ans %= mod;
        u = vtx[vtx[u].top].fa;
    }
    ans += query(1, 1, n, min(vtx[u].dfn, vtx[v].dfn), max(vtx[u].dfn, vtx[v].dfn)) % mod;
    return ans % mod;
}

int main() {
    scanf("%d %d %d %d", &n, &m, &rt, &mod);
    for (int i = 1; i <= n; ++i) scanf("%d", &vtx[i].val);
    for (int i = 1; i < n; ++i) { int u, v;
        scanf("%d %d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs1(rt, 0, 1), dfs2(rt, rt);
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) { int opt;
        scanf("%d", &opt);
        if (opt == 1) { int u, v, val;
            scanf("%d %d %d", &u, &v, &val);
            opt1(u, v, val);
        } else if (opt == 2) { int u, v;
            scanf("%d %d", &u, &v);
            printf("%d\n", opt2(u, v));
        } else if (opt == 3) { int u, val;
            scanf("%d %d", &u, &val);
            modify(1, 1, n, vtx[u].dfn, vtx[u].dfn + vtx[u].sz - 1, val);
        } else if (opt == 4) { int u;
            scanf("%d", &u);
            printf("%d\n", query(1, 1, n, vtx[u].dfn, vtx[u].dfn + vtx[u].sz - 1));
        }
    }
    return 0;
}

OI-树链剖分 OI-数据结构-线段树

仅有一条评论

  1. %神,求补实链剖分

treap 学习笔记
上一篇 «
弱智图论复习笔记
» 下一篇
© 2019 - 2019 bwt's blog.
...... visits · ...... visitors