发布于 由東風谷早苗（こちやさなえ）

树链剖分

将树上的点按照一定方式分为许多条链，从而将在树上的区间操作转移到线性数据结构上，减少时间复杂度的同时维护许多有用的信息。

常用的剖分依据有重链剖分，实链剖分（Link-Cut Tree）等。一般称重链剖分为树链剖分。

我们称子节点中子树大小最大的一个为重子，其他子节点称为轻子，与重子的连边称为重边，与其他子节点的连边称为轻边，多条重边首尾相连所形成的长链称为重链。

处理方式：两次深搜。

int size[MaxN], father[MaxN], heavy[MaxN]; // 第一次深搜维护信息
int stime, dfn[MaxN], top[MaxN];           // 第二次深搜信息

在第一次深搜中，记录每一个节点的父节点和子树大小，再找出每个节点的子节点中子树大小最大的节点。

void dfs1(int u, int fa) {
    father[u] = fa;
    size[u] = 1;
    for (node* p = h[u]; p != nullptr; p = p->next) {
        int v = p->v;
        if (v != fa) {
            dfs1(v, u);
            size[u] += size[v];
        }
    }
    int maxsize = 0, maxid = 0; // 找一个子树最大的子节点
    for (node* p = h[u]; p != nullptr; p = p->next) {
        int v = p->v;
        if (v != fa) {
            if (maxsize < size[v]) {
                maxsize = size[v];
                maxid = v;
            }
        }
    }
    heavy[u] = maxid;
}

在第二次深搜中，维护DFS序和该节点所在的重链的顶端节点，
然后以重子优先，轻子延后的顺序进行递归。

void dfs2(int u, int top) {
    dfn[u] = ++stime;
    hld::top[u] = top;
    if (heavy[u] != 0)
        dfs2(heavy[u], top); // 对于重子：和当前节点所在重链接到一起
    for (node* p = h[u]; p != nullptr; p = p->next) {
        int v = p->v;
        if (v != father[u] && v != heavy[u])
            dfs2(v, v); // 对于轻子：新开一条重链
    }
}

然后再以DFS序为标号构造线性数据结构（一般为线段树或树状数组）。

void init() {
    dfs1(1, 0);
    dfs2(1, 1);
    segmenttree::build();
}

通过画图，可以发现以下特点：
1. 每一个子树中所有节点的DFS序连续。（深搜特性保证这一性质）
2. 每一条重链上所有节点的DFS序连续。（重子优先的顺序和深搜特性共同保证这一性质）

根据以上两条性质，我们可以把对树上的区间和子树的询问/修改转移到线性结构的一定区间之上。

可以证明，从任意一点到根节点的路径上至多可以经过\(log_2 n\)条重链。

于是，当线性数据结构的查询/修改时间复杂度为\(O(log_2 n)\)时，我们可以在\(O(log_2 ^2 n)\)的时间里完成一次树上查询/修改操作。

方法：在区间查询/修改的同时向上跳至重链顶端的父节点，直到链顶为根节点。

int queryset(int x) {
    int ans = 0;
    while (top[x] != 1) {
        ans += segmenttree::query(dfn[top[x]], dfn[x]);
        segmenttree::set(dfn[top[x]], dfn[x], 1);
        x = father[top[x]];
    }
    ans += segmenttree::query(dfn[top[x]], dfn[x]);
    segmenttree::set(dfn[top[x]], dfn[x], 1);
    return ans;
}

同时，树链剖分还可以在\(O(log_2 n)\)的时间里处理最近公共祖先（LCA）问题，两节点同时往上跳时还可以处理区间修改/查询问题。（在第一遍DFS时还需维护节点深度）

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]])
            x = father[top[x]];
        else
            y = father[top[y]];
    }
    if (dep[x] < dep[y])
        return x;
    else
        return y;
}

在使用线段树/树状数组（查询/修改\(O(log_2 n)\)）时的时间复杂度：
第一遍深搜\(O(n)\)，第二遍深搜\(O(n)\)，查询\(O(log_2 ^2 n)\)，修改\(O(log_2 ^2 n)\)，普通LCA\(O(log_2 n)\)，带操作LCA\(O(log_2 ^2 n)\)

例题：洛谷P2146 [NOI2015]软件包管理器
安装时维护链上权值，删除时维护子树权值

/*
DOCUMENT NAME "20180724-luogu2146.cpp"
CREATION DATE 2018-07-24
SIGNATURE CODE_20180724_LUOGU2146
COMMENT [NOI2015]软件包管理器 / 树链剖分套线段树
*/

#include <cstdlib>
#include <iostream>
using namespace std;

constexpr int MaxN = 100000 + 10;

int read() {
    int val = 0;
    char c;
    while (!isdigit(c = getchar()));
    do {
        val = (val << 1) + (val << 3) + c - '0';
    } while (isdigit(c = getchar()));
    ungetc(c, stdin);
    return val;
}

void read(int& val) { val = read(); }
template<typename... Args>
void read(int& val, Args&... args) { val = read(); read(args...); }

void read(string& str) {
    str.clear();
    char c;
    while (isblank(c = getchar()) || iscntrl(c));
    do {
        str.push_back(c);
    } while (!isblank(c = getchar()) && !iscntrl(c));
    ungetc(c, stdin);
}

int n;

namespace graph {
    struct node {
        int v;
        node* next;
    };

    node* h[MaxN];
    node mem[2 * MaxN], *memtop = mem;
#define ALLOCATE (++memtop)

    void addedge(int u, int v) {
        node* p = ALLOCATE;
        p->v = v;
        p->next = h[u];
        h[u] = p;
        p = ALLOCATE;
        p->v = u;
        p->next = h[v];
        h[v] = p;
    }
}

namespace segmenttree {
    struct node {
        int sum, lazy;
        int left, right;
        node* lson, *rson;
    };

    node* root;
    node mem[2 * MaxN], *memtop = mem;

    void build(int left = 1, int right = n, node*& p = root) {
        p = ALLOCATE;
        p->left = left;
        p->right = right;
        if (left == right) {
            p->sum = 0;
            p->lazy = -1;
            p->lson = p->rson = nullptr;
        }
        else {
            p->lazy = -1;
            int mid = (left + right) / 2;
            build(left, mid, p->lson);
            build(mid + 1, right, p->rson);
            //p->sum = p->lson->sum + p->rson->sum;
            p->sum = 0;
        }
    }

    void pushdown(node* p) {
        if (p == nullptr || p->lazy == -1)
            return;
        p->sum = (p->right - p->left + 1)*p->lazy;
        if (p->lson != nullptr)
            p->lson->lazy = p->lazy;
        if (p->rson != nullptr)
            p->rson->lazy = p->lazy;
        p->lazy = -1;
    }

    void set(int left, int right, int val, node* p = root) {
        pushdown(p);
        if (p->left == left && p->right == right) {
            p->lazy = val;
            return;
        }
        if (p->lson->right >= right)
            set(left, right, val, p->lson);
        else if (p->rson->left <= left)
            set(left, right, val, p->rson);
        else {
            set(left, p->lson->right, val, p->lson);
            set(p->rson->left, right, val, p->rson);
        }
        pushdown(p);
        pushdown(p->lson);
        pushdown(p->rson);
        p->sum = p->lson->sum + p->rson->sum;
    }

    int query(int left, int right, node* p = root) {
        pushdown(p);
        if (p->left == left && p->right == right)
            return p->sum;
        if (p->lson->right >= right)
            return query(left, right, p->lson);
        else if (p->rson->left <= left)
            return query(left, right, p->rson);
        else
            return (query(left, p->lson->right, p->lson) +
                    query(p->rson->left, right, p->rson));
    }
}

namespace hld {
    using namespace graph;
    int size[MaxN], father[MaxN], heavy[MaxN];
    int stime, dfn[MaxN], top[MaxN];

    void dfs1(int u, int fa) {
        father[u] = fa;
        size[u] = 1;
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v;
            if (v != fa) {
                dfs1(v, u);
                size[u] += size[v];
            }
        }
        int maxsize = 0, maxid = 0;
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v;
            if (v != fa) {
                if (maxsize < size[v]) {
                    maxsize = size[v];
                    maxid = v;
                }
            }
        }
        heavy[u] = maxid;
    }

    void dfs2(int u, int top) {
        dfn[u] = ++stime;
        hld::top[u] = top;
        if (heavy[u] != 0)
            dfs2(heavy[u], top);
        for (node* p = h[u]; p != nullptr; p = p->next) {
            int v = p->v;
            if (v != father[u] && v != heavy[u])
                dfs2(v, v);
        }
    }

    void init() {
        dfs1(1, 0);
        dfs2(1, 1);
        segmenttree::build();
    }

    int install(int x) {
        int ans = 0;
        while (top[x] != 1) {
            ans += dfn[x] - dfn[top[x]] + 1 - segmenttree::query(dfn[top[x]], dfn[x]);
            segmenttree::set(dfn[top[x]], dfn[x], 1);
            x = father[top[x]];
        }
        ans += dfn[x] - dfn[top[x]] + 1 - segmenttree::query(dfn[top[x]], dfn[x]);
        segmenttree::set(dfn[top[x]], dfn[x], 1);
        return ans;
    }

    int uninstall(int x) {
        int ans = segmenttree::query(dfn[x], dfn[x] + size[x] - 1);
        segmenttree::set(dfn[x], dfn[x] + size[x] - 1, 0);
        return ans;
    }
}


int m;

int main(int argc, char* argv[]) {
    using namespace graph;
    using namespace hld;

    read(n);
    int x;
    for (int i = 2; i <= n; i++) {
        read(x);
        addedge(i, x + 1);
    }

    init();

    read(m);
    string str;
    for (int i = 1; i <= m; i++) {
        read(str);
        read(x);
        if (str == "install")
            printf("%d\n", install(x + 1));
        else if (str == "uninstall")
            printf("%d\n", uninstall(x + 1));
    }

    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注