本地源文件：docs/ds__seg-in-seg.md

线段树套线段树

常见用途

在算法竞赛中，我们有时需要维护多维度信息．在这种时候，我们经常需要树套树来记录信息．

我们考虑用树套树如何实现在二维平面上进行单点修改，区域查询．我们考虑外层的线段树，最底层的 11 到 𝑛n 个节点的子树，分别代表第 11 到第 𝑛n 行的线段树．那么这些底层的节点对应的父节点，就代表其两个子节点的子树所在的一片区域．

通常情况下，我们不可能对于外层线段树的每一个结点都建立一颗子线段树，空间需求过大．树套树一般采取动态开点的策略．单次修改，我们会涉及到外层线段树的 log⁡𝑛log⁡n 个节点，且对于每个节点的子树涉及 log⁡𝑛log⁡n 个节点，所以单次修改产生的空间最多为 log2⁡𝑛log2⁡n．

对于询问操作，我们考虑我们在外层线段树上进行 log⁡𝑛log⁡n 次操作，每次操作会在一个内层线段树上进行 log⁡𝑛log⁡n 次操作，所以时间复杂度为 log2⁡𝑛log2⁡n．修改操作，与询问操作复杂度相同，也为 log2⁡𝑛log2⁡n．

陌上花开将第一维排序处理，然后用树套树维护第二维和第三维．

第二维查询

---|---

第二维修改

---|---

第三维查询

---|---

第三维修改

---|---