树套树类问题 课件-2021-2022学年中学生信息学奥林匹克竞赛数据结构（难点）精讲

树套树类问题 信息学奥林匹克竞赛知识点（难点）精讲——数据结构【尖端】 偏序维护 即每次对满足多维的一个限制的所有数进行操作 多维的限制：每个点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的数个数 13 区别 普通树状数组用到的数据结构：支持修改值，查询值——变量 所以普通的树状数组可以用一个数组来维护 树状数组套平衡树用到的数据结构：支持插入一个值，查询小于一个值的数个数——平衡树 所以树状数组套平衡树可以用一个平衡树的数组维护 区别 变量每次访问是O( 1 )的，所以树状数组时间复杂度是O( logn ) 平衡树每次访问是O( log size )的，所以树状数组套平衡树的最坏时间复杂度是O( log^2n )的 由于不是每棵平衡树都满，所以这里带一个小常数，然而平衡树常数比较