登录
← 返回首页 | 代码片段 › 4 树上问题 › 4.2 树链剖分 › 树链剖分 / 搜索
JSON MD

4.2 树链剖分

树链剖分+MOD shulianpoufenMOD
219 行
CPP JSON
【树链剖分(Heavy-Light Decomposition)——带 MOD 版】 ▪ dfs1(u, p) — 第一次 DFS:计算 parent、depth、sz(子树大小)、heavy(重儿子) ▪ dfs2(u, h) — 第二次 DFS:分配 pos(线段树位置/DFS 序)、top(重链顶部),优先遍历重儿子保证重链连续 ▪ build(datas, tree, rt, l, r) — 线段树建树,O(N) ▪ pushDown(tree, rt, len) — 下传懒标记,O(1) ▪ query(tree, rt, l, r, ql, qr) — 线段树区间查询(含 MOD),O(log N) ▪ updateRange(tree, rt, l, r, ul, ur, val) — 线段树区间更新(含 MOD),O(log N) ▪ queryPath(u, v) — 查询树上路径 u↔v 的权值和:反复跳深度较深的 top,每次跳 O(log N),总计 O(log² N) ▪ updatePath(u, v, val) — 更新树上路径 u↔v 的权值,同理 O(log² N) 剖分 O(N),每次路径/子树操作 O(log² N)。适用于树上路径权值修改/查询(含取模)。
C++ 219 行 CPP
const int MAXN = 1e5 + 5;  // 最大节点数
int N, M, R, P;  // 节点数、操作数、根节点、模数
vector<int> adj[MAXN];  // 邻接表存储树结构
int val[MAXN];  // 节点初始权值

// 树链剖分相关变量
int parent[MAXN];  // 父节点
int depth[MAXN];   // 节点深度
int sz[MAXN];      // 子树大小
int heavy[MAXN];   // 重儿子
int pos[MAXN];     // 节点在线段树中的位置
int top[MAXN];     // 所在重链的顶部节点
int current_pos;   // 当前DFS序位置

// 线段树节点结构
struct node {
    int data;  // 节点值
    int lazy;  // 懒标记
    node() : data(0), lazy(0) {}
};

vector<node> tree;  // 线段树

// 构建线段树
void build(const vector<int>& datas, vector<node>& tree, int rt, int left, int right) {
    if (left == right) {
        tree[rt].data = datas[left];
        return;
    }
    int mid = left + (right - left) / 2;
    build(datas, tree, 2 * rt, left, mid);
    build(datas, tree, 2 * rt + 1, mid + 1, right);
    tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;
}

// 下传懒标记
void pushDown(vector<node>& tree, int rt, int len) {
    if (tree[rt].lazy != 0) {
        tree[rt * 2].data = (tree[rt * 2].data + tree[rt].lazy * (len - len / 2)) % P;
        tree[rt * 2].lazy = (tree[rt * 2].lazy + tree[rt].lazy) % P;
        tree[rt * 2 + 1].data = (tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2)) % P;
        tree[rt * 2 + 1].lazy = (tree[rt * 2 + 1].lazy + tree[rt].lazy) % P;
        tree[rt].lazy = 0;
    }
}

// 线段树区间查询
int query(vector<node>& tree, int rt, int left, int right, int ql, int qr) {
    if (ql > right || qr < left) {
        return 0;
    }
    if (ql <= left && qr >= right) {
        return tree[rt].data;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    int leftsum = query(tree, 2 * rt, left, mid, ql, qr);
    int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
    return (leftsum + rightsum) % P;
}

// 线段树区间更新
void updateRange(vector<node>& tree, int rt, int left, int right, int ul, int ur, int value) {
    if (ul > right || ur < left) return;
    if (ul <= left && ur >= right) {
        tree[rt].data = (tree[rt].data + value * (right - left + 1)) % P;
        tree[rt].lazy = (tree[rt].lazy + value) % P;
        return;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    updateRange(tree, 2 * rt, left, mid, ul, ur, value);
    updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
    tree[rt].data = (tree[2 * rt].data + tree[2 * rt + 1].data) % P;
}

// 第一次DFS:计算父节点、深度、子树大小和重儿子
void dfs1(int u, int p) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    sz[u] = 1;
    heavy[u] = 0;
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[heavy[u]]) {
                heavy[u] = v;
            }
        }
    }
}

// 第二次DFS:进行重链剖分,计算DFS序和重链顶部
void dfs2(int u, int p, int chain_top) {
    pos[u] = ++current_pos;
    top[u] = chain_top;
    if (heavy[u]) {
        dfs2(heavy[u], u, chain_top);
    }
    for (int v : adj[u]) {
        if (v != p && v != heavy[u]) {
            dfs2(v, u, v);
        }
    }
}

// 路径更新:将x到y路径上的节点值都加上z
void pathUpdate(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z);
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    updateRange(tree, 1, 1, N, pos[x], pos[y], z);
}

// 路径查询:查询x到y路径上的节点值之和
int pathQuery(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        res = (res + query(tree, 1, 1, N, pos[top[y]], pos[y])) % P;
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    res = (res + query(tree, 1, 1, N, pos[x], pos[y])) % P;
    return res;
}

// 子树更新:将以x为根的子树所有节点值加上z
void subtreeUpdate(int x, int z) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    updateRange(tree, 1, 1, N, l, r, z);
}

// 子树查询:查询以x为根的子树所有节点值之和
int subtreeQuery(int x) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    return query(tree, 1, 1, N, l, r);
}

// 求两个节点的最近公共祖先(LCA)
int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) {
            swap(x, y);
        }
        x = parent[top[x]];
    }
    return depth[x] < depth[y] ? x : y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> R >> P;
    for (int i = 1; i <= N; ++i) {
        cin >> val[i];
    }
    for (int i = 1; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    // 第一次DFS预处理
    dfs1(R, 0);
    current_pos = 0;
    // 第二次DFS进行重链剖分
    dfs2(R, 0, R);

    // 构建线段树
    vector<int> datas(N + 1);
    for (int i = 1; i <= N; ++i) {
        datas[pos[i]] = val[i] % P;
    }

    tree.resize(4 * (N + 1));
    build(datas, tree, 1, 1, N);

    // 处理操作
    while (M--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {  // 路径更新
            int x, y, z;
            cin >> x >> y >> z;
            pathUpdate(x, y, z);
        } else if (cmd == 2) {  // 路径查询
            int x, y;
            cin >> x >> y;
            cout << pathQuery(x, y) << '\n';
        } else if (cmd == 3) {  // 子树更新
            int x, z;
            cin >> x >> z;
            subtreeUpdate(x, z);
        } else if (cmd == 4) {  // 子树查询
            int x;
            cin >> x;
            cout << subtreeQuery(x) << '\n';
        }
    }

    return 0;
}
树链剖分 shulianpoufen
219 行
CPP JSON
【树链剖分(Heavy-Light Decomposition)——无 MOD 版】 ▪ dfs1(u, p) — 第一次 DFS:计算 parent、depth、sz、heavy(重儿子) ▪ dfs2(u, h) — 第二次 DFS:分配 pos(DFS 序)、top(重链顶部),优先遍历重儿子 ▪ build(datas, tree, rt, l, r) — 线段树建树,O(N) ▪ pushDown(tree, rt, len) — 下传懒标记,O(1) ▪ query(tree, rt, l, r, ql, qr) — 线段树区间查询(无 MOD),O(log N) ▪ updateRange(tree, rt, l, r, ul, ur, val) — 线段树区间更新(无 MOD),O(log N) ▪ queryPath(u, v) / updatePath(u, v, val) — 树上路径查询/更新,O(log² N) 与 ID=27 功能一致但不含模数,适用于不需要取模的树上路径/子树操作。
C++ 219 行 CPP
const int MAXN = 1e5 + 5;  // 最大节点数
int N, M, R;  // 节点数、操作数、根节点
vector<int> adj[MAXN];  // 邻接表存储树结构
int val[MAXN];  // 节点初始权值

// 树链剖分相关变量
int parent[MAXN];  // 父节点
int depth[MAXN];   // 节点深度
int sz[MAXN];      // 子树大小
int heavy[MAXN];   // 重儿子
int pos[MAXN];     // 节点在线段树中的位置
int top[MAXN];     // 所在重链的顶部节点
int current_pos;   // 当前DFS序位置

// 线段树节点结构
struct node {
    int data;  // 节点值
    int lazy;  // 懒标记
    node() : data(0), lazy(0) {}
};

vector<node> tree;  // 线段树

// 构建线段树
void build(const vector<int>& datas, vector<node>& tree, int rt, int left, int right) {
    if (left == right) {
        tree[rt].data = datas[left];
        return;
    }
    int mid = left + (right - left) / 2;
    build(datas, tree, 2 * rt, left, mid);
    build(datas, tree, 2 * rt + 1, mid + 1, right);
    tree[rt].data = tree[2 * rt].data + tree[2 * rt + 1].data;
}

// 下传懒标记
void pushDown(vector<node>& tree, int rt, int len) {
    if (tree[rt].lazy != 0) {
        tree[rt * 2].data = tree[rt * 2].data + tree[rt].lazy * (len - len / 2);
        tree[rt * 2].lazy = tree[rt * 2].lazy + tree[rt].lazy;
        tree[rt * 2 + 1].data = tree[rt * 2 + 1].data + tree[rt].lazy * (len / 2);
        tree[rt * 2 + 1].lazy = tree[rt * 2 + 1].lazy + tree[rt].lazy;
        tree[rt].lazy = 0;
    }
}

// 线段树区间查询
int query(vector<node>& tree, int rt, int left, int right, int ql, int qr) {
    if (ql > right || qr < left) {
        return 0;
    }
    if (ql <= left && qr >= right) {
        return tree[rt].data;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    int leftsum = query(tree, 2 * rt, left, mid, ql, qr);
    int rightsum = query(tree, 2 * rt + 1, mid + 1, right, ql, qr);
    return leftsum + rightsum;
}

// 线段树区间更新
void updateRange(vector<node>& tree, int rt, int left, int right, int ul, int ur, int value) {
    if (ul > right || ur < left) return;
    if (ul <= left && ur >= right) {
        tree[rt].data = tree[rt].data + value * (right - left + 1);
        tree[rt].lazy = tree[rt].lazy + value;
        return;
    }
    pushDown(tree, rt, right - left + 1);
    int mid = left + (right - left) / 2;
    updateRange(tree, 2 * rt, left, mid, ul, ur, value);
    updateRange(tree, 2 * rt + 1, mid + 1, right, ul, ur, value);
    tree[rt].data = tree[2 * rt].data + tree[2 * rt + 1].data;
}

// 第一次DFS:计算父节点、深度、子树大小和重儿子
void dfs1(int u, int p) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    sz[u] = 1;
    heavy[u] = 0;
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[heavy[u]]) {
                heavy[u] = v;
            }
        }
    }
}

// 第二次DFS:进行重链剖分,计算DFS序和重链顶部
void dfs2(int u, int p, int chain_top) {
    pos[u] = ++current_pos;
    top[u] = chain_top;
    if (heavy[u]) {
        dfs2(heavy[u], u, chain_top);
    }
    for (int v : adj[u]) {
        if (v != p && v != heavy[u]) {
            dfs2(v, u, v);
        }
    }
}

// 路径更新:将x到y路径上的节点值都加上z
void pathUpdate(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        updateRange(tree, 1, 1, N, pos[top[y]], pos[y], z);
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    updateRange(tree, 1, 1, N, pos[x], pos[y], z);
}

// 路径查询:查询x到y路径上的节点值之和
int pathQuery(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (depth[top[x]] > depth[top[y]]) {
            swap(x, y);
        }
        res = res + query(tree, 1, 1, N, pos[top[y]], pos[y]);
        y = parent[top[y]];
    }
    if (depth[x] > depth[y]) {
        swap(x, y);
    }
    res = res + query(tree, 1, 1, N, pos[x], pos[y]);
    return res;
}

// 子树更新:将以x为根的子树所有节点值加上z
void subtreeUpdate(int x, int z) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    updateRange(tree, 1, 1, N, l, r, z);
}

// 子树查询:查询以x为根的子树所有节点值之和
int subtreeQuery(int x) {
    int l = pos[x];
    int r = pos[x] + sz[x] - 1;
    return query(tree, 1, 1, N, l, r);
}

// 求两个节点的最近公共祖先(LCA)
int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (depth[top[x]] < depth[top[y]]) {
            swap(x, y);
        }
        x = parent[top[x]];
    }
    return depth[x] < depth[y] ? x : y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> R;
    for (int i = 1; i <= N; ++i) {
        cin >> val[i];
    }
    for (int i = 1; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    // 第一次DFS预处理
    dfs1(R, 0);
    current_pos = 0;
    // 第二次DFS进行重链剖分
    dfs2(R, 0, R);

    // 构建线段树
    vector<int> datas(N + 1);
    for (int i = 1; i <= N; ++i) {
        datas[pos[i]] = val[i];
    }

    tree.resize(4 * (N + 1));
    build(datas, tree, 1, 1, N);

    // 处理操作
    while (M--) {
        int cmd;
        cin >> cmd;
        if (cmd == 1) {  // 路径更新
            int x, y, z;
            cin >> x >> y >> z;
            pathUpdate(x, y, z);
        } else if (cmd == 2) {  // 路径查询
            int x, y;
            cin >> x >> y;
            cout << pathQuery(x, y) << '\n';
        } else if (cmd == 3) {  // 子树更新
            int x, z;
            cin >> x >> z;
            subtreeUpdate(x, z);
        } else if (cmd == 4) {  // 子树查询
            int x;
            cin >> x;
            cout << subtreeQuery(x) << '\n';
        }
    }

    return 0;
}
已复制