当前位置：首页 > web >正文

【算法笔记】树套树

web 2025/6/23 19:04:45

一、前言

在面对二维区间统计问题时，比如：

查询某个一维区间中，大于某个值的数的个数
对一个序列同时支持区间查询 + 单点修改

我们常用的一维数据结构（如线段树、树状数组）往往显得力不从心。此时，我们可以考虑一种高效的数据结构组合：树套树。

二、什么是树套树？

“树套树”顾名思义，就是一棵树中的每个节点再套一棵树。

最常见的树套树结构是：

外层：线段树/树状数组，按照下标维护区间
内层：平衡树（如 STL multiset 或手写 Treap/Splay）维护该区间内的值集合

通过树套树，可以实现如下操作：

单点修改某个值
查询区间中小于/大于某值的数的个数
查询区间第 $k$ 小数值（需平衡树）

三、典型问题：二维数点问题

问题描述

给定一个长度为 $n$ 的数组 $a$ ，支持以下操作：

修改某个位置的值
查询某个区间 $[l, r]$ 内，**有多少个数大于 $k$

例如：

a = [1, 5, 2, 4, 3]查询 (l=2, r=4, k=2)：返回 2（即 5 和 4）

四、树套树实现思路

1. 外层线段树（按下标划分）

我们构建一棵线段树，每个节点维护一个子区间 $[l, r]$ 对应的数值集合（支持动态插入和删除）。

2. 内层平衡树（或 multiset）

每个线段树节点用一个 multiset 保存该区间内所有数值，并支持：

插入 / 删除某个值（用于修改操作）
查询大于某个值的个数（用 upper_bound 实现）

五、代码实现（C++）

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int a[N];struct SegmentTree {int l, r;multiset<int> s;SegmentTree* left = nullptr;SegmentTree* right = nullptr;SegmentTree(int l, int r): l(l), r(r) {if (l == r) {s.insert(a[l]);} else {int m = (l + r) / 2;left = new SegmentTree(l, m);right = new SegmentTree(m + 1, r);s.insert(left->s.begin(), left->s.end());s.insert(right->s.begin(), right->s.end());}}void update(int pos, int old_val, int new_val) {s.erase(s.find(old_val));s.insert(new_val);if (l == r) return;int m = (l + r) / 2;if (pos <= m) left->update(pos, old_val, new_val);else right->update(pos, old_val, new_val);}int query(int ql, int qr, int k) {if (qr < l || r < ql) return 0;if (ql <= l && r <= qr) {return s.end() - s.upper_bound(k);}return left->query(ql, qr, k) + right->query(ql, qr, k);}
};

使用方式

int main() {int n, q;cin >> n >> q;for (int i = 1; i <= n; ++i) cin >> a[i];SegmentTree* root = new SegmentTree(1, n);while (q--) {string op;cin >> op;if (op == "Q") {int l, r, k;cin >> l >> r >> k;cout << root->query(l, r, k) << '\n';} else if (op == "M") {int x, v;cin >> x >> v;root->update(x, a[x], v);a[x] = v;}}
}