树上差分 - 树上操作 题解

· · 个人记录

原题

有一个 N 个节点的树，其中点 1 是根。初始点权值都是 0。

一个节点的深度定义为其父节点的深度 +1。特别的，根节点的深度定义为 1。

现在需要支持一系列以下操作：给节点 u 的子树中，深度在 l 和 r 之间的节点的权值（这里的深度依然从整个树的根节点开始计算），都加上一个数 delta 。

问完成所有操作后，各节点的权值是多少。

思路

本题使用离线算法，首先记录所有更新数据。

然后用 dfs(x) 表示正在更新以 x 节点为根的子树，用差分数组 a 来记录权值的变化。

如果当前点 x 有要更新的，那么就进行差分，代码如下：

s[l]+=d;
s[r+1]-=d;

因为我们在枚举 x 子树，x 子树内所有 dep\in [l,r] 的权值都要增加 d

所以我们差分时，感觉要维护单点修改，区间查询

是不是要用 BIT（树状数组）呢？答案显然是否定的。

其实只要写一个差分数组，在 dfs 的时候顺带着求和即可。

这时候就只用 O(1) 来更新，在递归过程直接做+当前 a_i 即可，也是 O(1)。

总时间复杂度为 O(n)，可过。

但由于数据较为毒瘤，另设有多组 hack 数据，所以，该题必须要用链式前向星和适当的输入优化来卡常。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7, M = 1e9 + 7, ma = 12347;
#define int long long
int l[N], r[N], d[N], n, q, x, ans[N], a[N], h;
vector<int> g[N], v[N];
void dfs(int x, int dep, int z) {
    for (int i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if (r[y] < dep)
            continue;
        if (l[y] < dep)
            l[y] = dep;
        a[l[y]] += d[y];
        a[r[y] + 1] -= d[y];
    }
    z += a[dep];
    ans[x] = z;
    for (int i = 0; i < g[x].size(); ++i) dfs(g[x][i], dep + 1, z);
    for (int i = 0; i < v[x].size(); ++i) {
        int y = v[x][i];
        if (r[y] < dep)
            continue;
        a[l[y]] -= d[y];
        a[r[y] + 1] += d[y];
    }
}
signed main() {
    scanf("%lld", &n);
    for (int i = 2; i <= n; ++i) {
        scanf("%lld", &x);
        g[x].push_back(i);
    }
    scanf("%lld", &q);
    for (int i = 1; i <= q; ++i) {
        scanf("%lld%lld%lld%lld", &x, l + i, r + i, d + i);
        v[x].push_back(i);
    }
    dfs(1, 1, 0);
    for (int i = 1; i <= n; ++i) h = (h * ma + ans[i]) % M;
    //本题采用 hash 的方式生成数据，实际和直接输入是一样的
    printf("%lld\n", h);
    return 0;
}