线段树套线段树

概述

树套树用一种数据结构的每个节点再套一种数据结构，以支持多维度查询，常见组合有线段树套线段树、线段树套平衡树、树状数组套主席树等。它能在线处理区间内某值的排名、区间第 k 小、区间前驱后继，并支持单点修改，本质是用外层结构索引一维、内层结构维护另一维的信息。相比主席树，它以支持修改换取更大的常数与空间。附 P3380 二逼平衡树作为综合例题，涵盖上述全部操作。

参考资料

• 线段树套线段树 - OI Wiki

简介

树套树 用一种数据结构的每个节点再套一种数据结构，以支持多维度查询，如 线段树套线段树、线段树套平衡树、树状数组套主席树等，能在线处理区间内某值的排名、区间第 $k$ 小、区间前驱后继并支持单点修改。

例题

洛谷 P3380 【模板】树套树

维护一个序列，支持五种操作：查询某值在区间内的排名、查询区间第 $k$ 小、单点修改、查询区间内某值的前驱与后继。