(
课件网) 树套树类问题 信息学奥林匹克竞赛知识点（难点）精讲———数据结构【尖端】 偏序维护 即每次对满足多维的一个限制的所有数进行操作 多维的限制：每个点i有ai,bi,ci…等不同的属性 每次对l1<=ai<=r1,l2<=bi<=r2…的i进行一次查询操作，或插入一个单点 如何维护？ 1.Range Tree 2.K-D Tree 3.Quad Tree , Octree 4.R-Tree Range Tree 其实就是狭义上的树套树 树套树 能在O( logn^d )的复杂度内进行一次d维偏序的范围查询 能在O( logn^d )的复杂度内进行一次d维偏序的单点修改 空间为O( nlogn^(d-1) )，可以优化到O( n(logn/loglogn)^(d-1) )，不过这个应该没人会所以可以无视掉 树套树 具体来说什么树套什么树是有关系的 树套树 如果要维护d维，出于方便设每维的值大小是v的一个偏序 高维树状数组 本质就是树状数组的嵌套 时间复杂度O( logv^d )，空间复杂度O( v^d ) 可以通过预先高维离散化来做到 时间复杂度O( logv^d )，空间复杂度O( nlogv^d ) 不过这个基本上无意义 ~ 接下来只讨论二维情况 因为三维情况下常数和空间都起飞了，就没见过一个三维的题 关于树套树 我最开始也觉得这东西很牛逼，很码农 （后面发现也就5分钟的事。。。） 感觉能用到的树套树基本上都可以用树状数组套平衡树/线段树来写 函数化数据结构的思想 我们以树状数组套平衡树作为例子来介绍一下树套树 普通的树状数组 维护一个序列支持： 1.把x位置的值加上y 2.查询一个区间的和 树状数组套平衡树 维护一个序列支持： 1.把x位置的值改为y 2.查询一个区间中小于y的数个数 区别 普通树状数组用到的数据结构：支持修改值，查询值———变量 所以普通的树状数组可以用一个数组来维护 树状数组套平衡树用到的数据结构：支持插入一个值，查询小于一个值的数个数———平衡树 所以树状数组套平衡树可以用一个平衡树的数组维护 区别 变量每次访问是O( 1 )的，所以树状数组时间复杂度是O( logn ) 平衡树每次访问是O( log size )的，所以树状数组套平衡树的最坏时间复杂度是O( log^2n )的 由于不是每棵平衡树都满，所以这里带一个小常数，然而平衡树常数比较大，所以还是比较慢的 所以 只需要先写一个平衡树，然后写个树状数组就行了 Expansion 树状数组套平衡树在绝大多数场合下都够用了 其他常见的还有树状数组套Trie，线段树套平衡树，可以类比树状数组套平衡树的实现方法来实现，即将内部的树看做一个和外部树独立的数据结构 对线段树套平衡树的解释 维护一个序列 1.单点修改 2.区间[l,r]中 <= k的元素个数 线段树套平衡树 普通的线段树： 每个节点维护一个区间的和 每次修改更新O(logn)个节点的和 每次查询时用O(logn)个不相交节点的和拼出这次询问的区间 线段树套平衡树： 每个节点维护一个平衡树，表示区间内部的元素排好序后的平衡树 每次修改更新O(logn)个节点的平衡树 每次查询时用O(logn)个不相交节点中<=k的元素个数拼出这次询问的区间 Comparison 对比一下几种常见的树套树的优缺点 树状数组套树 优势：好写，常数 劣势：只能维护支持差分的信息，如果不能满足差分则基本上不能使用 树状数组套树 套平衡树：时间复杂度O( logn^2 )，空间复杂度O( nlogn ) 优势：空间 劣势：平衡树没有简单的可以在多个平衡树上二分的方法，区间kth这种询问会多一个log（其实可以不多log的，但这个多树二分的科技常数比较大，而且较为复杂，在OI界应该算很不普及吧） 树状数组套树 套Trie：时间复杂度O( lognlogv )，空间复杂度O( nlognlogv ) 优势：可以简单地在多个Trie上二分 劣势：空间（可以通过特殊的技巧达到O( nlogn )的空间复杂度） 线段树套树 套平衡树：时间复杂度O( logn^2 )，空间复杂 ... ...
