树套树

2025-12-13T19:37:29+08:00 | 3 分钟阅读 | 更新于 2025-12-13T19:37:29+08:00 | 0 次阅读

@ Jason Chan

介绍了一些常用的树套树，以及需要注意的点。

树套树的原理

普通的线段树、树状数组等数据结构，只能在一个维度上维护信息。在静态下，可以用可持久化拓展维度，但是难以修改。

树套树，顾名思义，就是数据结构套数据结构。在第一层数据结构上套上第二层数据结构，进而实现二维信息的维护。如下是用树状数组套上其他数据结构的示例，可以视作在二维平面上维护具有可减性数据的示例。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void add (int x, int L, int R, int k) {
    for (; x <= n; x += lowbit (x)) 
        modify (rt[x], L, R, k);
}

int qry (int x, int L,int R) {
    int res = 0;
    for (; x; x -= lowbit (x))
        res += querysum (L, R);
    return res;
}

int qry (int x1, int y1, int x2, int y2) {
    return qry (x2, y1, y2) - qry (x1 - 1, y1, y2);
}

敏锐的你应该注意到了，如果对于第二维度都开满一层数据结构，空间复杂度直线飙升到 $\mathcal O(n^2)$ 级别，显然具有十足的冗余数据。因此在考虑数据结构的实现时，应在内部采用可以动态变化大小的数据结构，如动态开点线段树、平衡树之类的数据结构。第一维度采用普通的线段树或者树状数组都可。

维护的信息实际上取决于外部与内部树的结构关系，一般来说空间复杂度会达到 $\mathcal O(n\log^2 n)$，取决于信息维度的利用。另外，一次修改或者查询的复杂度，对于套了 $k$ 维数据结构，查询一次的复杂度为各个数据结构查询复杂度之积。下面见几个常用的树套树例子。

常用树套树

权值线段树套动态开点区间线段树

可用于求动态区间 $k$ 大问题，见模板题 P3332 [ZJOI2013] K大数查询，可在线地求区间 $k$ 大。空间复杂度为

 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


#include <iostream>

using ll = long long;

using namespace std;

const int N = 5e4 + 10;

int n, m;
int rt[N * 500], tot, ls[N * 500], rs[N * 500], lazy[N * 500];
ll sum[N * 500];

void upd (int& u, int k, int l, int r) {
    if (!u) u = ++ tot;
    sum[u] += (r - l + 1) * 1ll * k;
    lazy[u] += k;
}

void pushdown (int u, int l, int r) {
    int mid = l + r >> 1;
    upd (ls[u], lazy[u], l, mid);
    upd (rs[u], lazy[u], mid + 1, r);
    lazy[u] = 0;
}

void pushup (int u) {
    sum[u] = sum[ls[u]] + sum[rs[u]];
}

void modify (int& u, int ql, int qr, int k, int l = 1, int r = n) {
    if (!u) u = ++ tot;
    if (l >= ql && r <= qr) return upd (u, k, l, r);
    pushdown (u, l, r);
    int mid = l + r >> 1;
    if (ql <= mid) modify (ls[u], ql, qr, k, l, mid);
    if (qr > mid)  modify (rs[u], ql, qr, k, mid + 1, r);
    pushup (u);
}

void add (int u, int l, int r, int ql, int qr, int k) {
    modify (rt[u], ql, qr, 1);
    if (l == r) return ;
    int mid = l + r >> 1;
    if (k <= mid) add (u << 1, l, mid, ql, qr, k);
    else          add (u << 1 | 1, mid + 1, r, ql, qr, k);
}

ll qrysum (int u, int ql, int qr, int l = 1, int r = n) {
    if (!u) return 0;
    if (l >= ql && r <= qr) return sum[u];
    pushdown (u, l, r);
    ll ret = 0, mid = l + r >> 1;
    if (ql <= mid) ret += qrysum (ls[u], ql, qr, l, mid);
    if (qr > mid)  ret += qrysum (rs[u], ql, qr, mid + 1, r);
    return ret;
}

int qry (int u, int l, int r, int ql, int qr, ll k) {
    if (l == r) return l;
    int mid = l + r >> 1;
    ll rsum = qrysum (rt[u << 1 | 1], ql, qr);
    if (rsum < k) return qry (u << 1, l, mid, ql, qr, k - rsum);
    else          return qry (u << 1 | 1, mid + 1, r, ql, qr, k);
}

int main (void) {

    scanf ("%d%d", &n, &m);
    while (m --) {
        int opt, l, r;
        ll c;
        scanf ("%d%d%d%lld", &opt, &l, &r, &c);
        if (opt == 1) add (1, 1, 2 * n + 1, l, r, c + n + 1);
        else          printf ("%d\n", qry (1, 1, 2 * n + 1, l, r, c) - n - 1);
    }

    return 0;
}

实际上，内部的区间树可以直接标记永久化，可以优化时空，见下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


void add (int& u, int l, int r, int ql, int qr, int k) {
    if (!u) u = ++ tot;
    sum[u] += (min (r, qr) - max (ql, l) + 1) * k;
    if (l >= ql && r <= qr) return lazy[u] += k, void ();
    if (ql <= mid) add (ls[u], l, mid, ql, qr, k);
    if (qr > mid)  add (rs[u], mid + 1, r, ql, qr, k);
}

int qrysum (int u, int l, int r, int ql, int qr) {
    if (!u) return 0;
    if (l >= ql && r <= qr) return sum[u];
    int res = (min (r, qr) - max (l, ql) + 1) * lazy[u];
    if (ql <= mid) res += qrysum (ls[u], l, mid, ql, qr);
    if (qr >  mid) res += qrysum (rs[u], mid + 1, r, ql, qr);
    return res;
}