跳转至

线段树合并

有时，我们需要给树上每一个节点维护一个一维 dp 数组。若其转移过程满足以下条件，可以使用线段树合并优化：

  • 每个节点的 \(dp\) 值都是由其子节点转移而来；
  • \(dp_u\) 的一个下标位置由 \(dp_v\) 中相同位置下标转移而来；
  • （可选）\(dp_u\) 的一个下标位置 \(i\) 额外需要 \(dp_u\) 或 \(dp_v\) 在 \([1,i]\) 区间前缀和来转移；

例题

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

题目大意

村落里的一共有 \(n\) 座房屋，并形成一个树状结构。救济粮分 \(m\) 次发放，每次选择两个房屋 \((x, y)\)，然后对于 \(x\) 到 \(y\) 的路径上（含 \(x\) 和 \(y\)）每座房子里发放一袋 \(z\) 类型的救济粮。

我们想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

我们发现如果暴力枚举路径上的每个节点，时间复杂度就已经炸了。因此我们首先考虑使用数据结构维护路径信息，或者使用树上差分。因为每个节点还可能有多个元素，所以直接使用数据结构维护路径，时间和空间都会爆炸。

考虑树上差分。对于一条路径 \((u,v)\)，我们修改 \(x\)，\(y\)，\(lca(x,y)\)，\(fa[lca(x,y)]\)，并在第二次 dfs 的时候做子树求和。记

  • \(g_{u,j}\) 表示节点 \(u\) 中 \(j\) 类型救济粮的差分数组；
  • \(f_{u,j}\) 表示发放完所有粮食之后，节点 \(u\) 中 \(j\) 类型救济粮的总数量；

由此得到：

\[ f_{u,j}=g_{u,j}+\sum_{v\in to[u]}f_{v,j} \]

这种和子树数组对应位置直接相加的式子可以使用线段树合并优化。

具体的，对于每条操作路径，我们向 \(x\) 和 \(y\) 节点对应的线段树（动态开点的权值线段树）的 \(w\) 位置 \(+1\)，\(lca(x,y)\) 对应的位置 \(-1\)。

接着，在 dfs 中将子节点 \(v\) 的线段树合并到 \(u\) 的线段树上。把所有子节点的线段树都合并之后，当前线段树就是 \(u\) 的 \(f_{u}\) 数组。直接查询最大值即可。

时间复杂度证明

当两棵线段树有一个重合的节点时，才会继续向下递归，产生 \(O(1)\) 的时间复杂度。同时两个重合的节点被合并成了一个，这等价于删除了一个节点。由此得到：每产生 \(O(1)\) 的时间复杂度，都会删除 \(1\) 个节点。

因为初始情况下一共有 \(O(n\log V)\) 个节点，并且合并过程中不会产生新的节点，因此删除节点数一定小于等于 \(n\log V\)。由上面的结论得到，时间复杂度的上界是 \(O(n\log V)\)。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<iostream>
#define int long long
using namespace std;
const int N = 1E5 + 10;
const int Z = 1E5;
const int LOGN = 20;

struct myPair {
    int pos, val;
};

inline const myPair &max(const myPair &a, const myPair &b) {
    if(a.val >= b.val) return a;
    return b;
}

struct Edge {
    int v;
    int next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m;
int anc[N][LOGN], dep[N];

void dfs0(int u, int fa) {
    dep[u] = dep[fa] + 1;
    anc[u][0] = fa;
    for(int i = 1; i < LOGN; i++) {
        anc[u][i] = anc[ anc[u][i - 1] ][i - 1];
    }
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == fa) continue;
        dfs0(v, u);
    }
}

int getlca(int x, int y) {
    if(dep[x] < dep[y]) {
        swap(x, y);
    }
    for(int i = LOGN - 1; i >= 0; i--) {
    if(dep[anc[x][i]] >= dep[y]) x = anc[x][i]; 
    }
    if(x == y) return x;
    for(int i = LOGN - 1; i >= 0; i--) {
        if(anc[x][i] != anc[y][i]) {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}

int ans[N];
int lc[4 * 20 * N], rc[4 * 20 * N], nn;
myPair mx[4 * 20 * N];
int rt[N];

void push_up(int p) {
    mx[p] = max(mx[lc[p]], mx[rc[p]]);
}

void insert(int &p, int l, int r, int q, int v) {
    if(p == 0) p = ++nn;
    if(l == r) {
        mx[p].val += v;
        mx[p].pos = l;
        return;
    }
    int mid = (l + r) >> 1;
    if(mid >= q) insert(lc[p], l, mid, q, v);
    else insert(rc[p], mid + 1, r, q, v);
    push_up(p);
}

int merge(int p1, int p2, int l, int r) {
    if(p1 == 0 || p2 == 0) return p1 | p2;
    if(l == r) {
        mx[p1].val += mx[p2].val;
        return p1;
    }
    int mid = (l + r) >> 1;
    lc[p1] = merge(lc[p1], lc[p2], l, mid);
    rc[p1] = merge(rc[p1], rc[p2], mid + 1, r);
    push_up(p1);
    return p1;
}

void dfs(int u, int f) {
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == f) continue;
        dfs(v, u);
        rt[u] = merge(rt[u], rt[v], 1, Z);
    }
    if(mx[rt[u]].val != 0) ans[u] = mx[rt[u]].pos;
}

signed main() {

    cin >> n >> m;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs0(1, 0);

    for(int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        int lca = getlca(x, y);
        insert(rt[x], 1, Z, z, 1);
        insert(rt[y], 1, Z, z, 1);
        insert(rt[lca], 1, Z, z, -1);
        insert(rt[anc[lca][0]], 1, Z, z, -1);
    }

    dfs(1, 0);

    for(int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

子树深度查询

题目大意

给定一棵有根树，根节点为 \(1\) 号节点，每个点有点权。有 \(q\) 次询问，每次询问给定 \(u,l,r\)，询问在 \(u\) 子树内所有满足 \(dep[v]\in [l,r]\) 的节点 \(v\) 的点权的最大值。

二维数点做不了，因为两个维度都有上下界的限制，且答案不可差分。

这里我们使用线段树合并解决。使用线段树维护深度，可以 \(O(\log n)\) 求出区间点权最大值。因为深度是不变的，满足使用线段树合并的要求，直接套板子即可。

P6773 [NOI2020] 命运

题目大意

给定一棵 \(n\)（\(n\le 5\times 10^5\)）个节点的有根树和 \(m\)（\(m \le 5\times 10^5\)）条返祖链。现在要求用黑白两种颜色给所有边染色，使得每条返祖链都有至少一条边是白色的。问染色方案数对 \(998244353\) 取模的结果。

详见我的题解。

P5298 [PKUWC2018] Minimax

做法高度相似于上一题，也需要前缀和处理，以及线段树乘法 tag。