在 OI/ICPC 界，树套树的经典问题主要围绕多维动态维护、动态区间查询、二维空间修改查询等展开。

经典问题

1.P3517 [CQOI2011] 动态逆序对

【题意简化】给定一个 $1 \sim n(\le 10^5)$ 的排列，每次删除一个数，求每次删除前序列的逆序对总数。

【分析】本题正常解法是 CDQ 分治，如果要求强制在线，可以采用 "树状数组套权值线段树".

树状数组维护位置, 权值线段树维护值对应点的数量。

每次删除位置 $p$ 的值 $v$，对答案的影响就是去掉 $[1,p-1]$ 大于 $v$ 的个数，去掉 $[p+1,n]$ 小于 v 的个数.

内层线段树动态开点, 每次修改增加 $\log{n}$ 个节点, 那么空间复杂度就是 $O(n+n\log{v})$ ,$v$ 是值域.

时间复杂度是 $O((n+m)\log{n}*\log{v})$.

【参考代码】树套树参考代码

2. P2617 Dynamic Rankings

【题意简化】支持单点修改，查询区间 $[L, R]$ 的第 $K$ 小值。

【分析】本题可以采用 整体二分 求解，如果要求强制在线，可以采用树状数组套权值线段树解决. 本题是理解和应用"树套树"的核心.

外层树状数组维护位置，内层采用权值线段树，为了保证空间够用，线段树动态开点。对于 $x$ 处的树状数组维护横坐标 $[x-lowbit[x]+1,x]$ , 此处对应一颗权值线段树，维护值对应的个数。

区间查询 $[L, R]$ 的第 $K$ 小 , 需要在多颗线段树上二分查找.

在 $[L,R]$ 内所有线段树查询第 $K$ 小, 树状数组对应的线段树对应值域相同， 计算出所有值域左侧节点数量 l_sum ，如果小于等于 $K$ , 那么就递归到值域左侧，否则在值域右侧查找 K-l_sum , 直到值域长度为 1 。

当然计算时，需要 $[1,R]$ 内所有贡献减去 $[1,l-1]$ 内所有线段树值域左侧的贡献。

使用临时数组，记录线段树节点编号，加贡献和减贡献分开存, 临时数组长度是 $O(\log{n})$.

核心查询代码如下

int temp_l[20],temp_r[20];
int cnt_l,cnt_r;
//多颗线段树对应值值域相同都是 [lval,rval]
//temp_r[1...cnt_r] 对结果是+ 
//temp_l[1...cnt_l] 对结果是-

int query(int lval,int rval,int k)  
{
    if(lval==rval)return lval;
    int mid=(lval+rval)>>1;
    
    int l_sum=0;  //计算 [lval,mid] 中的个数
    for(int i=1;i<=cnt_r;i++)l_sum+=sum[lc[temp_r[i]]];
    for(int i=1;i<=cnt_l;i++)l_sum-=sum[lc[temp_l[i]]];

    if(k<=l_sum)  //去值域左侧查询
    {
        //将当前线段树替换成左儿子
        for(int i=1;i<=cnt_l;i++)temp_l[i]=lc[temp_l[i]];
        for(int i=1;i<=cnt_r;i++)temp_r[i]=lc[temp_r[i]];

        return query(lval,mid,k);
    }
    else
    {
        //替换为右儿子
        for(int i=1;i<=cnt_l;i++)temp_l[i]=rc[temp_l[i]];
        for(int i=1;i<=cnt_r;i++)temp_r[i]=rc[temp_r[i]];
        
        return query(mid+1,rval,k-l_sum);
    } 
}

对值域离散化之后,值域范围也是 $n$ ,那么时间复杂度就是 $O(n\log^2{n})$ ，空间复杂度是 $O(n\log^2{n})$

【参考代码】树套树写法

3. P3380 【模板】树套树

【题意简化】支持单点修改, 查区间内排名、查区间内第 $K$ 大、查区间内前驱、查区间内后继。

【分析】本题是"树套树"模板题.

方法一: 线段树套平衡树

外层线段树维护位置，内层平衡树值对应的个数．

线段树套平衡树，线段树每个节点创建一颗以值为序的平衡树，那么这颗平衡树就包含了第一维度(位置) $[l,r]$ 内所有元素。

1. 查询 $k$ 在区间 $[l,r]$ 内的排名: 第一维 [l,r] 对应线段树 $\log{n}$ 个节点，每个节点对应一个平衡树，只需要这些平衡树上小于 $k$ 的个数，再加 $1$ 就是答案。 单次时间复杂度为 $O(n\log^2{n})$ 。

2. 查询区间 $[l,r]$ 排名为 $k$ 的值: 需要先在值域上二分答案，对于二分的 $mid$ , 可以查询 $mid$ 在 $[l,r]$ 内的排名，如果排名小于 $k$ ，就在值域左侧查询 $[lval,mid]$ ,否则到右侧查询，即需要调用 1 操作。 单次时间复杂度是 $O(\log^3{n})$。

3. 修改某一位置：在线段树中找到包含 pos 的所有区间，在对应的平衡树上修改即可。单次时间复杂度为 $O(n\log^2{n})$

4. 查前驱:对应多棵平衡树上找小于 $k$ 的最大值. 后继同理

线段树套平衡树参考代码: 点击

方法二: 权值线段树套线段树或平衡树(推荐)

方法一是常规思路，比较容易想，时间瓶劲在于“查询区间内排名 k 的值” ，需要在值域上二分，在判定答案，时间复杂度就是 $O(\log^3(n))$

转换一下思路，外层记录数值，内层记录位置。动态开点权值线段树套平衡树解决。

这种架构，最大的优势在于查询区间第 $k$ 大的值时，可以避免二分答案带来的多一个 $\log$ 的开销。

具体拆解到每个操作如下：

1. 查询 $k$ 在区间 $[l, r]$ 内的排名

在区间 $[l, r]$ 内查找严格小于 $k$ 的数的个数 $+ 1$。

• 操作：在外层权值线段树中，我们需要查询值域在 $[0, k-1]$ 范围内的信息。这个值域区间会被拆分成 $O(\log V)$ 个外层线段树的节点。对于这 $O(\log V)$ 个节点，我们分别进入其内层的平衡树，查询在下标区间 $[l, r]$ 内的元素个数（即查询值 $\le r$ 的排名减去 $< l$ 的排名）。
• 复杂度：$O(\log V \cdot \log n)$。

2. 查询区间 $[l, r]$ 内排名为 $k$ 的值

从外层权值线段树的根节点（值域 $[0, 10^8]$）开始向下走。假设当前节点的左子树代表的值域为 $[V_l, mid]$，我们进入左子树的内层平衡树，查询位于下标区间 $[l, r]$ 的元素个数 $cnt$。

• 如果 $cnt \ge k$，说明第 $k$ 小的数在左子树，向左走；

• 如果 $cnt < k$，说明在右子树，令 $k = k - cnt$，向右走。

• 复杂度：需要往下走 $\log V$ 层，每层在内层平衡树中查询一次下标区间，花费 $O(\log n)$。总复杂度为 $O(\log V \cdot \log n)$。(这是该方法优于传统做法的核心点)

3. 修改某一位置上的数值

单点修改。假设将位置 $pos$ 的旧值 $v_{old}$ 修改为新值 $v_{new}$。

• 在外层权值线段树中，找到从根节点到 $v_{old}$ 的路径（共 $\log V$ 个节点），在这些节点的内层平衡树中删除下标 $pos$。
• 同样，找到从根到 $v_{new}$ 的路径，在这些节点的内层平衡树中插入下标 $pos$。

插入和删除路径长度均为 $\log V$，每次平衡树操作为 $O(\log n)$。总复杂度为 $O(\log V \cdot \log n)$。

4 & 5. 查询前驱 / 后继

可以直接复用操作 1 和操作 2。例如查前驱，先查 $k$ 在 $[l, r]$ 的排名 $rnk$，再查 $[l, r]$ 中排名为 $rnk - 1$ 的数即可（后继同理，查 $k+1$ 的排名）。

空间复杂度：由于每个元素（共 $n$ 个）会被插入到外层线段树的 $\log V$ 个节点的内层平衡树中，总共会产生 $n \log V$ 个平衡树节点。 空间复杂度为 $O(n \log V)$。 按 $N=2 \times 10^5, \log V = 27$ 计算，大约产生 $5.4 \times 10^6$ 个节点。本题给出了 2.00GB 的超大内存，这个空间消耗游刃有余。 可以对值域离散化,进一步优化空间。

综上所述，整体时间复杂度是 $O((n + m) \log V \cdot \log n)$。

当然外层维护值，查询的区间和，那么外层也可直接用树状数组做，也就是权值树状数组套线段树。

方法三: 树状数组套权值线段树(推荐方法)

树状数组维护位置，权值线段树维护值对应的数量。

对于查询 $k$ 的排名, 就是查询小于 $k$ 的个数。核心思想查看 P2617 Dynamic Rankings

树状数组套权值线段树参考代码:点击

4. P3332 [ZJOI2013] K 大数查询

【题意简化】有 $N$ 个位置，初始为空。

操作 1：在区间 $[L, R]$ 中每个位置加入一个数 $c$。 操作 2：查询区间 $[L, R]$ 中所有数里的第 $K$ 大。

【分析】整体二分，或者树套树

外层线段树维护值域，内层线段树维护位置。

5. [IOI2001] 手机 / Mokia (Luogu P4390)

矩阵的单点修改与区间查询

分析:一维线段树 套 一维线段树（或者 CDQ 分治 / 树状数组套动态开点线段树）。

6. P3437 [POI 2006] TET-Tetris 3D

【题意简化】二维平面 $(x\in[1,S],y\in[1,S])$，在线操作：

1. 给定矩形 $(x1,x2,y1,y2)$，先查询该矩形内最大高度 $h$，再把矩形全部赋值为 $(h+w)$；
2. 全局查询整个平面最大值。

【分析】

结构：外层 x 轴线段树，内层 y 轴线段树，标记永久化维护区间 max

特点：纯二维平面区间赋值、区间最值，强制在线，只能线段树套线段树，无法用平衡树套线段树。

7.P5445 [APIO2019] 路灯

转化为 矩形修改，查询,可以使用树套树，或者 CDQ 分治。

注意:

面对多维度信息的题目时，如果题目没有要求强制在线，我们还可以考虑 CDQ 分治，或者 整体二分 等分治算法，来避免使用高级数据结构，减少代码实现难度．

---

学习完毕

{{ select(1) }}

• YES
• NO