浅谈树套树

kaikai_qwq · 2026-10-16 19:00:03 · 算法·理论

树套树，顾名思义，就是外层树形数据结构，内层套一个树形数据结构。

所以直接放例题吧。

P4390 [BalkanOI 2007] Mokia 摩基亚

维护一个 w \times w 的矩阵，初始全为 0，支持以下操作：

• 1 x y a：将位置 (x,y) 的值增加 a；
• 2 x1 y1 x2 y2：查询子矩阵 [x_1,x_2] \times [y_1,y_2] 内所有值之和。

操作次数：修改不超过 160000 次，查询不超过 10000 次；1 \le w \le 2 \times 10^6，0 < a \le 10000。

树套树板子题。

使用树状数组套动态开点线段树，每个树状数组上的位置，存储对应位置的线段树的根。

对于每个内层线段树，维护对应列区间和。

对于单点修改 (x, y) 增加 a，外层树状数组按 x 在 BIT 上遍历，遍历的每个点修改对应的动态开点线段树上的位置。

查询 [1, x] \times [y_1, y_2] 时，外层树状数组同样按 x 在 BIT 上遍历，对于 x 每个 BIT 上的节点，在它挂的内层线段树上查询列区间 [y_1, y_2] 的和。

子矩阵 [x_1, x_2] \times [y_1, y_2] 的和，查询 (x_2, y_1, y_2) - (x_1 - 1, y_1, y_2)。

时空复杂度均为 O(Q\log^2 w)，其中 Q 为操作次数。

由于这题空间限制 125\text{MB}，单纯树状数组套线段树空间是无法通过的，内层需要使用平衡树，这不是我们讨论的范围，所以放个 60pts 的树套树代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3.6e5 + 10;
const int MAXM = 1.7e5 + 10;
int n;
int lsh[MAXN], tot;
struct SegmentTree {
    int root[MAXN], idx;
    struct node {
        int ls, rs;
        int val;
    } w[MAXN * 30];
    void pushup(int u) {
        w[u].val = w[w[u].ls].val + w[w[u].rs].val;
    }
    void update(int &u, int L, int R, int p, int x) {
        if (!u) u = ++idx;
        if (L == R) {
            w[u].val += x;
            return;
        }
        int mid = (L + R) >> 1;
        if (p <= mid) update(w[u].ls, L, mid, p, x);
        else update(w[u].rs, mid + 1, R, p, x);
        pushup(u);
    }
    int query(int &u, int L, int R, int l, int r) {
        if (!u) return 0;
        if (L >= l && R <= r) return w[u].val;
        int mid = (L + R) >> 1;
        int res = 0;
        if (l <= mid) res += query(w[u].ls, L, mid, l, r);
        if (r > mid) res += query(w[u].rs, mid + 1, R, l, r);
        return res;
    }
} tr;
struct FenwickTree {
    int lowbit(int x) { return x & -x;}
    void add(int x, int y, int z) {
        for (int i = x; i <= tot; i += lowbit(i)) tr.update(tr.root[i], 1, tot, y, z);
    }
    int query(int x, int y1, int y2) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr.query(tr.root[i], 1, tot, y1, y2);
        return res;
    }
    int qry(int x1, int x2, int y1, int y2) {
        return query(x2, y1, y2) - query(x1 - 1, y1, y2);
    }
} BIT;
struct qry {
    int op;
    int x, y, a;
    int x1, y1, x2, y2;
} q[MAXM];
int cnt;
int id(int x) {
    return lower_bound(lsh + 1, lsh + tot + 1, x) - lsh;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int op;
    cin >> op >> n;
    while (cin >> op) {
        if (op == 3) break;
        if (op == 1) {
            int x, y, a;
            cin >> x >> y >> a;
            q[++cnt] = {op, x, y, a, 0, 0, 0, 0};
            lsh[++tot] = x;
            lsh[++tot] = y;
        } else {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            q[++cnt] = {op, 0, 0, 0, x1, y1, x2, y2};
            lsh[++tot] = x1, lsh[++tot] = x2;
            lsh[++tot] = y1, lsh[++tot] = y2;
        }
    }
    sort(lsh + 1, lsh + tot + 1);
    tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
    for (int i = 1; i <= cnt; i++) {
        if (q[i].op == 1) {
            int x = id(q[i].x);
            int y = id(q[i].y);
            BIT.add(x, y, q[i].a);
        } else {
            int x1 = id(q[i].x1);
            int x2 = id(q[i].x2);
            int y1 = id(q[i].y1);
            int y2 = id(q[i].y2);
            cout << BIT.qry(x1, x2, y1, y2) << '\n';
        }
    }
    return 0;
}

P4175 [CTSC2008] 网络管理

给定一棵 n 个节点的树，每个点有一个延迟值 t_i。有 q 次操作：

对于不带修的查询，只需要树上每个点维护到根的答案，查询时则转换成第 k 小然后差分，查询 T_u + T_v - T_{\text{LCA}(u, v)} - T_{fa_{\text{LCA}(u, v)}}，在线段树上二分。

我们需要支持待修、树上前缀和，考虑外层树状数组。

修改需要修改整个子树，首先使用 dfn 序转换成序列问题。树状数组每个位置维护一棵主席树。

那么，对于 T_x，在 BIT 上分摊到了 O(\log n) 个节点，那么 T_x 相当于 BIT 上若干节点主席树之和，其他同理。

我们将 T_u, T_v, T_{\text{LCA}(u, v)}, T_{fa_{\text{LCA}(u, v)}} 对应 BIT 上的线段树集合记为 S_1, S_2, S_3, S_4。

然后使用 v = \sum_{u\in S_1} w_{ls_u} + \sum_{u\in S_2} w_{ls_u} - \sum_{u\in S_3} w_{ls_u} - \sum_{u\in S_4} w_{ls_u} 判断进行线段树上二分。

如果 k\le v，则向左边递归，令 S_1\sim S_4 所有点变成它的左儿子；否则，变成查询第 k - v 小，向右边递归，令 S_1\sim S_4 所有点变成它的右儿子。

复杂度：时空复杂度均为 O(q\log n\log V)，时间复杂度离散化后为 O(q\log^2 n)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10;
const int V = 1e8;
int n, m;
int a[MAXN];
vector <int> G[MAXN];
vector <int> S1, S2, S3, S4;
struct qry {
    int a, b, k;
} q[MAXN];
int lsh[MAXN << 2], tot;
struct SegmentTree {
    int root[MAXN], idx;
    struct node {
        int ls, rs;
        int val;
    } w[MAXN << 5];
    void pushup(int u) {
        w[u].val = w[w[u].ls].val + w[w[u].rs].val;
    }
    void update(int &u, int l, int r, int p, int x) {
        if (!u) u = ++idx;
        if (l == r) {
            w[u].val += x;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(w[u].ls, l, mid, p, x);
        else update(w[u].rs, mid + 1, r, p, x);
        pushup(u);
    }
    int query(int l, int r, int k) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int v = 0;
        for (auto x : S1) v += w[w[x].ls].val;
        for (auto x : S2) v += w[w[x].ls].val;
        for (auto x : S3) v -= w[w[x].ls].val;
        for (auto x : S4) v -= w[w[x].ls].val;
        if (k <= v) {
            for (auto &x : S1) x = w[x].ls;
            for (auto &x : S2) x = w[x].ls;
            for (auto &x : S3) x = w[x].ls;
            for (auto &x : S4) x = w[x].ls;
            return query(l, mid, k); 
        }
        for (auto &x : S1) x = w[x].rs;
        for (auto &x : S2) x = w[x].rs;
        for (auto &x : S3) x = w[x].rs;
        for (auto &x : S4) x = w[x].rs;
        return query(mid + 1, r, k - v);
    }
} tr;
struct LCA {
    int dfn[MAXN], top[MAXN], siz[MAXN], dep[MAXN], fa[MAXN], son[MAXN], tot;
    void dfs1(int u, int f) {
        fa[u] = f;
        siz[u] = 1;
        dep[u] = dep[f] + 1;
        for (auto v : G[u]) {
            if (v == f) continue;
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[son[u]] < siz[v]) son[u] = v;
        }
    }
    void dfs2(int u, int Top) {
        top[u] = Top;
        dfn[u] = ++tot;
        if (son[u]) dfs2(son[u], Top);
        for (auto v : G[u]) {
            if (v == fa[u] || v == son[u]) continue;
            dfs2(v, v);
        }
    }
    int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            x = fa[top[x]];
        }
        return dep[x] < dep[y] ? x : y;
    }
} banana;
struct FenwickTree {
    int lowbit(int x) { return x & -x;}
    void add(int x, int y, int v) {
        for (int i = x; i <= n; i += lowbit(i)) tr.update(tr.root[i], 1, n + m, y, v);
    }
    void insert(vector <int> &S, int x) {
        for (int i = x; i; i -= lowbit(i)) S.push_back(tr.root[i]);
    }
    void update(int l, int r, int y, int v) {
        add(l, y, v);
        add(r + 1, y, -v);
    }
} BIT;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lsh[++tot] = a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    banana.dfs1(1, 0);
    banana.dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        cin >> q[i].k;
        if (q[i].k == 0) {
            cin >> q[i].a >> q[i].b;
            lsh[++tot] = q[i].b;
        } else cin >> q[i].a >> q[i].b;
    }
    sort(lsh + 1, lsh + tot + 1);
    tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
    for (int i = 1; i <= m; i++)
        if (q[i].k == 0) q[i].b = lower_bound(lsh + 1, lsh + tot + 1, q[i].b) - lsh;
    for (int i = 1; i <= n; i++) BIT.update(banana.dfn[i], banana.dfn[i] + banana.siz[i] - 1, a[i], 1);
    for (int i = 1; i <= m; i++) {
        if (q[i].k == 0) {
            BIT.update(banana.dfn[q[i].a], banana.dfn[q[i].a] + banana.siz[q[i].a] - 1, a[q[i].a], -1);
            a[q[i].a] = q[i].b;
            BIT.update(banana.dfn[q[i].a], banana.dfn[q[i].a] + banana.siz[q[i].a] - 1, a[q[i].a], 1);
        } else {
            S1.clear(), S2.clear(), S3.clear(), S4.clear();
            int u = q[i].a, v = q[i].b, w = banana.lca(q[i].a, q[i].b);
            int z = banana.fa[w];
            BIT.insert(S1, banana.dfn[u]);
            BIT.insert(S2, banana.dfn[v]);
            BIT.insert(S3, banana.dfn[w]);
            if (z) BIT.insert(S4, banana.dfn[z]);
            int nnn = banana.dep[u] + banana.dep[v] - 2 * banana.dep[w] + 1;
            if (q[i].k > nnn) {
                cout << "invalid request!\n";
                continue;
            }
            q[i].k = nnn - q[i].k + 1;
            int ans = tr.query(1, n + m, q[i].k);
            cout << lsh[ans] << '\n';
        }
    }
    return 0;
}

P3437 [POI 2006] TET-Tetris 3D

有一个 D \times S 的地面，N 个长方体依次垂直下落，不会旋转或翻转。每个长方体由 d_i, s_i, w_i, x_i, y_i 描述，底面投影为 (x_i, y_i) 到 (x_i+d_i, y_i+s_i)。

长方体落到当前地面上方，即它的底面高度等于其投影区域内当前最高方块的高度。求所有方块落下后最高方块的高度。

考虑线段树套线段树。

• 对于外层线段树，显然按行建立，每一个节点维护 [l, r] 行的最大值/标记的内层线段树根编号。
• 对于内层线段树，每个节点维护对应行区间中列 [l, r] 列最大值/标记。

但是这题不能懒标记下传。

外层线段树懒标记不是普通的数，是一棵内层线段树。 下传标记，需要把父结点的内层线段树合并到子结点的内层线段树中。 那么这是一次线段树合并，复杂度是 O(S) 的，显然不行。 同时，每次 pushup 也需要合并两棵线段树，同样不行。

注意到，在本题中，区间修改的值比修改前的最大值要大。那么，每个数只会变大，不会变小。

于是，考虑标记永久化。

标记永久化的思想为：

更新时，沿途修改经过结点的信息，并对完全覆盖的区间打上标记，但不下传标记。 查询时，把沿途经过的结点的标记累加起来，用于修正查询结果。

对于本题的树套树，标记永久化和一维也类似：

• 更新外层时，更新沿途的内层标记线段树。
• 如果完全包含修改区间，更新内层最大值线段树。
• 查询时，和沿途标记线段树最大值取 \max。

时间复杂度：O(n\log S\log D)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
int D, S, n;
struct SegmentTree1 {
    struct node {
        int val;
        int tag;
        int ls, rs;
    } w[MAXN << 5];
    int idx;
    void update(int &u, int L, int R, int l, int r, int x) {
        if (!u) u = ++idx;
        w[u].tag = max(w[u].tag, x);
        if (L >= l && R <= r) {
            w[u].val = max(w[u].val, x);
            return;
        }
        int mid = (L + R) >> 1;
        if (l <= mid) update(w[u].ls, L, mid, l, r, x);
        if (r > mid) update(w[u].rs, mid + 1, R, l, r, x);
    }
    int query(int u, int L, int R, int l, int r) {
        if (!u) return 0;
        if (L >= l && R <= r) return max(w[u].tag, w[u].val);
        int mid = (L + R) >> 1;
        int res = w[u].val;
        if (l <= mid) res = max(res, query(w[u].ls, L, mid, l, r));
        if (r > mid) res = max(res, query(w[u].rs, mid + 1, R, l, r));
        return res;
    }
} tr1;
struct SegmentTree2 {
    struct node {
        int val, tag;
    } w[MAXN << 5];
    void update(int u, int L, int R, int l, int r, int U, int D, int x) {
        tr1.update(w[u].tag, 1, S, U, D, x);
        if (L >= l && R <= r) {
            tr1.update(w[u].val, 1, S, U, D, x);
            return;
        }
        int mid = (L + R) >> 1;
        if (l <= mid) update(u << 1, L, mid, l, r, U, D, x);
        if (r > mid) update(u << 1 | 1, mid + 1, R, l, r, U, D, x);
    }
    int query(int u, int L, int R, int l, int r, int U, int D) {
        if (!u) return 0;
        if (L >= l && R <= r) return max(tr1.query(w[u].val, 1, S, U, D), tr1.query(w[u].tag, 1, S, U, D));
        int mid = (L + R) >> 1;
        int res = tr1.query(w[u].val, 1, S, U, D);
        if (l <= mid) res = max(res, query(u << 1, L, mid, l, r, U, D));
        if (r > mid) res = max(res, query(u << 1 | 1, mid + 1, R, l, r, U, D));
        return res;
    }
} tr2;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> D >> S >> n;
    for (int i = 1; i <= n; i++) {
        int d, s, w, x, y;
        cin >> d >> s >> w >> x >> y;
        int mx = tr2.query(1, 1, D, x + 1, x + d, y + 1, y + s);
        tr2.update(1, 1, D, x + 1, x + d, y + 1, y + s, mx + w);
    }
    cout << tr2.query(1, 1, D, 1, D, 1, S);
    return 0;
}

P3157 [CQOI2011] 动态逆序对

给定 1 \sim n 的一个排列 a，依次删除 m 个元素，每次删除前输出当前序列的逆序对数。

逆序对定义为满足 i < j 且 a_i > a_j 的有序对 (i,j) 的数量。

首先，考虑删掉一个数 i，会造成那些影响。

需要在原先的基础上，减去 [1, i - 1] 中 > a_i 的，再减去 [i + 1, n] 中 < a_i 的。

看似，这个东西可以静态主席树。

但是，如果逆序对 (i, j) 中 a_i, a_j 都被删除，那么就会重复统计。

于是考虑树状数组套主席树。

每次删掉一个数，需要在 [i + 1, n] 的版本都删除掉 a_i 这个数，也就是在 a_i 对应的位置减一，用树套树容易维护。

注意实现时需要从后往前建树状数组。

时空复杂度 O((n + m)\log^2 n)。

P5445 [APIO2019] 路灯

有 n+1 个站点和 n 条路段，每条路段有一盏路灯。第 i 盏灯亮时，出租车可以通过站点 i 到 i+1 的路段。

初始时给定每盏灯的状态。接下来 q 个时刻，每个时刻发生以下事件之一：

• toggle i：切换第 i 盏灯的状态；
• query a b：询问从 0 时刻到当前时刻，有多少个时刻满足出租车能从站点 a 到达站点 b（a < b）。

考虑转化为二维问题。

对于一个点对 (x, y)，在平面上对应一个点 (x, y)，点权为无后续时刻修改的情况下两点连通的时刻的数量。

那么对于查询操作，直接查询 (a, b) 的点权即可。注意若在当前时刻 a, b 仍然连通，需要将答案减去 q - t，因为把后面的时刻也算了。

对于修改操作，我们对于每个点，维护 l_x, r_x 表示 x 所在连通块左右端点。

• 当 x 由亮变灭时，首先将 [l_x, r_x] 分裂成 [l_x, x], [x + 1, r_x]。那么，[l_x, x + 1]\times [x, r_x] 这个矩阵，点权都减去 q - t。这意味着，不考虑接下来的修改，[l_x, x] 所有点和 [x + 1, r_x] 所有点都不会连通。
• 当 x 由灭变亮时，首先讲 [l_x, x], [x + 1, r_{x + 1}] 合并成一个连通块 [l_x, r_{x + 1}]。那么，[l_x, x + 1]\times [x, r_{x + 1}] 这个矩阵，点权都加上 q - t。这意味着，不考虑接下来的修改，[l_x, x] 所有点和 [x + 1, r_{x + 1}] 所有点都会连通。

对于单点查矩阵加，矩阵加拆分成四个单点修改，然后使用树状数组套线段树维护二维前缀和即可。

考虑怎么维护 l_x, r_x：

使用类似 ODT 的方法，使用 \texttt{set} 维护。 具体的，在 \texttt{set} 中存储所有连通块左右端点。首先，一次二分（lower_bound）找出属于的连通块，然后，合并时，删除原来两个连通块对应端点，加入合并后大连通块对应端点；分裂时，删除原来这个连通块端点，然后加入分裂的两个连通块端点。

时间复杂度 O(n\log^2 n)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 6e5 + 10;
int n, q;
int s[MAXN];
struct SegmentTree {
    int root[MAXN], idx;
    struct node {
        int ls, rs;
        int val;
    } w[MAXN << 5];
    void pushup(int u) {
        w[u].val = w[w[u].ls].val + w[w[u].rs].val;
    }
    void update(int &u, int l, int r, int p, int x) {
        if (!u) u = ++idx;
        if (l == r) {
            w[u].val += x;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(w[u].ls, l, mid, p, x);
        else update(w[u].rs, mid + 1, r, p, x);
        pushup(u);
    }
    int query(int u, int L, int R, int l, int r) {
        if (L >= l && R <= r) return w[u].val;
        int mid = (L + R) >> 1;
        int res = 0;
        if (l <= mid) res += query(w[u].ls, L, mid, l, r);
        if (r > mid) res += query(w[u].rs, mid + 1, R, l, r);
        return res;
    }
} tr;
// 注意 +1 否则 0 修改会炸
struct FenwickTree {
    int lowbit(int x) { return x & -x;}
    void add(int x, int y, int k) {
        for (int i = x; i <= n + 1; i += lowbit(i)) tr.update(tr.root[i], 1, n + 1, y, k);
    }
    int sum(int x, int y) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr.query(tr.root[i], 1, n + 1, 1, y);
        return res;
    }
    void upd(int x1, int y1, int x2, int y2, int k) {
        add(x2 + 1, y2 + 1, k);
        add(x1, y1, k);
        add(x1, y2 + 1, -k);
        add(x2 + 1, y1, -k);
    }
} BIT;
struct ODT {
    #define st auto
    struct node {
        int l, r;
        bool operator < (const node &a) const {
            return r < a.r;
        }
    };
    set <node> s;
    void init() {
        for (int i = 1; i <= n; i++) s.insert({i, i});
    }
    void merge(int l1, int r1, int l2, int r2) {
        s.erase({l1, r1});
        s.erase({l2, r2});
        s.insert({l1, r2});
    }
    void split(int l1, int r1, int l2, int r2) {
        s.erase({l1, r2});
        s.insert({l1, r1});
        s.insert({l2, r2});
    }
    bool is_same(int x, int y) {
        st it1 = s.lower_bound({0, x});
        st it2 = s.lower_bound({0, y});
        return (it1 -> l == it2 -> l);
    }
    #undef st
} odt;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    n++;
    odt.init();
    for (int i = 1; i < n; i++) {
        char ch;
        cin >> ch;
        s[i] = ch - '0';
        if (s[i]) {
            auto it = odt.s.lower_bound({0, i});
            odt.merge(it -> l, i, i + 1, i + 1);
        }
    }
    for (auto it : odt.s) BIT.upd(it.l, it.l, it.r, it.r, q);
    for (int i = 1; i <= q; i++) {
        string op;
        cin >> op;
        if (op[0] == 't') {
            int a;
            cin >> a;
            auto it = odt.s.lower_bound({0, a});
            int l1 = it -> l, r1 = a;
            int l2 = r1 + 1, r2 = 0;
            if (s[a]) {
                r2 = it -> r;
                odt.split(l1, r1, l2, r2);
                BIT.upd(l1, l2, r1, r2, i - q);
            } else {
                r2 = (++it) -> r;
                odt.merge(l1, r1, l2, r2);
                BIT.upd(l1, l2, r1, r2, q - i);
            }
            s[a] ^= 1;
        } else {
            int l, r;
            cin >> l >> r;
            int ans = BIT.sum(l, r);
            if (odt.is_same(l, r)) ans -= q - i;
            cout << ans << '\n';
        }
    }
    return 0;
}