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

根号数据结构 信息学奥林匹克竞赛知识点（难点）精讲——数据结构【尖端】 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的根节点的信息 分块的作用 所以如果在分治结构上很难快速合并某些信息，我们就可以利用分块来做 经典问题 维护一个序列 1.区间加 2.查询区间小于x的数个数 Solution 如果是单点修改，我们可以用树套树实现 但是区间修改后树套树无法快速合并信息 比如我们维护了cur的一个名次数据结构 cur的左儿子没有发生变化 cur的右儿子被整体加了 这样我们无法通过这两个儿子的名次数据结构快速维护出cur的名次数据结构 也无法直接在cur的名次数据结构上操作 所以分治结构无法在低复杂度解决这个问题 Solution 分块，维护每块的OV（就是排序后的数组） 每次区间加的时候 整块可以打一个标记 零散块可以重构 每次查询的时候 整块查询小于x的数，这个整块的标记为y（也就是说这一块所有数都加了y） 则等价于查整块的排序后的数组里面小于x-y的数的个数 这个可以二分 零散块就直接暴力查询块内在查询区间内的数是否满足条件 Complexity