在 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))$

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

1. 查询 k 在区间 [l,r] 的排名: 我们查询值在 [0,k-1] 中有多少个位置在给定区间内，再加一就是答案。

2. 查询区间 [l,r] 内排名为 k 的值: 直接在权值线段树上二分，查询值域左侧(线段树左子树)有 l_num 个节点落在区间 [l,r] 内，如果个数小于 k ，递归左子树查找，否则递归右子树查找 k-l_num ，递归边界值域长度为 1 停止返回。

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

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

对于查询 $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