根号数据结构课件-2021-2022学年中学生信息学奥林匹克竞赛数据结构（难点）精讲（333张PPT）

(课件网) 根号数据结构 信息学奥林匹克竞赛知识点（难点）精讲———数据结构【尖端】 Notice 如果没有专门说明 默认n = 1e5 , m = 1e5 分块基础 分块的分类 静态分块 动态分块 静态分块指的是放一些关键点，预处理关键点到关键点的信息来加速查询的，不能支持修改 目前认为：如果可以离线，静态分块是莫队算法的子集 动态分块指的是把序列分为一些块，每块维护一些信息，可以支持修改 动态分块基础 下列提到的分块默认为动态分块 分块基础 要实现： 1.区间加 2.区间和 朴素来做，可以有O(1)修改O(n)查询以及O(n)修改O(1)查询的暴力做法 这个问题可以套用根号平衡达到O( sqrt(n) )修改O( sqrt(n) )查询 我们可以把sqrt(n)个元素放一块里面维护 分块基础 我们把每次操作完整覆盖的块定义为“整块” 把每次操作没有完整覆盖的块定义为“零散块” 分块基础 每次操作最多经过O( sqrt(n) )个整块，以及2个零散块 所以我们可以O(1)维护整块信息，O( sqrt(n) )查询零散块信息 这样就达到了O( msqrt(n) )的复杂度 分块 一个度数 ，只有三层的树 分块 每次修改只用更新： 个size为1的节点以及2个size为 的节点 注意到我们不用维护那个size为n的根节点的信息 分块的作用 所以如果在分治结构上很难快速合并某些信息，我们就可以利用分块来做 经典问题 Solution 如果是单点修改，我们可以用树套树实现 但是区间修改后树套树无法快速合并信息 比如我们维护了cur的一个名次数据结构 cur的左儿子没有发生变化 cur的右儿子被整体加了 这样我们无法通过这两个儿子的名次数据结构快速维护出cur的名次数据结构 也无法直接在cur的名次数据结构上操作 所以分治结构无法在低复杂度解决这个问题 Solution 分块，维护每块的OV（就是排序后的数组） 每次区间加的时候 整块可以打一个标记 零散块可以重构 每次查询的时候 整块查询小于x的数，这个整块的标记为y（也就是说这一块所有数都加了y） 则等价于查整块的排序后的数组里面小于x-y的数的个数 这个可以二分 零散块就直接暴力查询块内在查询区间内的数是否满足条件 Complexity 设有x个块 查询复杂度： 整块O( log(n / x) ) * x 零散块O( n / x ) 修改复杂度： 整块O( 1 ) 零散块O( n / x ) （重构的时候用归并） 按照根号平衡算一算可以发现 总复杂度O( msqrt( nlogn ) ) 此时块大小为sqrt( nlogn ) Solution 大概有另外两个O( msqrt( n ) )的做法 不过没有什么太大的实用价值，写起来很麻烦，常数较大，不一定比O( msqrt( nlogn ) )做法快，也基本上没人会 所以这里就不讲了 [Ynoi2017] 由乃打扑克 Solution Solution Solution Solution 存在O( msqrt( nlogn ) )的算法，基于复杂的多序列二分，not practical 用根号平衡来优化数据结构复杂度 根号平衡 根号平衡 根号平衡 修改： 查询： 根号平衡 根号平衡 分块维护块内前缀和和块外前缀和 也就是说维护每个块块内前x数的和 以及维护前x的块的和 更新的时候分别更新这两个前缀和 查询的时候把这两个前缀和拼起来 根号平衡 修改： 查询： 根号平衡 维护一个序列，支持： O( sqrt(n) )区间加，O(1)查单点 根号平衡 直接分块 根号平衡 修改： 查询： 根号平衡 根号平衡 根号平衡 修改： 查询： 根号平衡 根号平衡 根号平衡 修改： 查询： 根号平衡 根号平衡 值域分块 对于每个数维护一下其在哪个块里面 对于每个块维护一个OV（有序表）表示这个块内的所有数存在的数，从小到大 这样我们修改的时候只会改变sqrt( n )个数所从属的块 查询的时候定位到其所属于的块，然后找到其在该块中对应的值 根号平衡 修改： 查询： CodeChef Chef and Churu 给长为n的序列，给定m个函数，每个函数为序列中第l ... ...