倍增分块与线段树底层分块
EnofTaiPeople
·
2023-02-15 21:55:51
·
题解
Part1 前言
这道题可以使用根号分块吗？我想了许久也没想出答案。
所以我打算学习一下倍增分块。
如果这题难点在于卡常的话，我倒不必急于去写这道题的代码和题解，然而这道题不仅不卡常，还具有十分有价值的倍增思想。
底层分块并不能算是在卡常，因为它确实优化了空间复杂度。
Part2 题意及前置知识
对区间大于 x 的数减去 x，区间求和。
前置知识：线段树，均摊复杂度分析。
### Part3 倍增分块的用法
倍增分块用处大多在于数值修改单调的情形，比如本题。
考虑将 $\lfloor\log_2a_i\rfloor$ 相同的 $a_i$ 放在同一个块内，每一个块开一棵维护区间 $[1,n]$ 的线段树，但只维护块内的数值和。
以下定义“变块”表示 $a_i$ 在修改时 $\log_2a_i$ 变小导致 $a_i$ 所在值域块产生变化。
考虑一次修改 $l,r,x$：
1. $\lfloor\log_2a_i\rfloor<\lfloor\log_2x\rfloor$，则 $a_i$ 所在块不会产生变化；
2. $\lfloor\log_2a_i\rfloor=\lfloor\log_2x\rfloor$，这时使用线段树最值剪枝找到块内所有 $a_i>x$，这时的 $a_i$ 一定会变块；
3. $\lfloor\log_2a_i\rfloor>\lfloor\log_2x\rfloor$，这时在区间 $[l,r]$ 的线段树上打懒标记，并线段树最值剪枝找到所有变块的数值。
倍增分块的优秀之处在于，每一个数字的变块次数最多为 $\log_2V$，总变块次数最多为 $n\log_2V$。
于是，对于第 $2$ 种，找到一个 $a_i>x$，复杂度为 $O(\log_2n)$，而这时会产生一次变块，所以是均摊 $O(n\log_2n\log_2V)$。
对于 第 $3$ 种，打标记复杂度为 $O(\log_2n)$，每找到一个需要变块的数字复杂度为 $O(\log_2n)$，这部分是均摊 $O(n\log_2n\log_2V)$。
查询就对每一个值域块分别查询就可以了。
### Part4 底层分块的意义
容易发现上面的空间复杂度是 $O(n\log_2V)$，而我们需要线性空间。
一个好方法是每一个块改为维护平衡树，这样可能时间卡常并且太难写所以我没去试，但用 AVL 应该可以卡过。
发现所有线段树建立的区间都是 $[1,n]$，而且最下面的几层最没有用却节点最多，所以可以将区间长度不再超过 $\log_2n$ 的节点不再新增叶子节点。
这样做为什么不影响时间复杂度？因为线段树区间查询的性质是每一次最多递归到 $O(1)$ 个叶子节点，所以时间不变。
### Part5 效率分析及改动
首先不一定要将 $2$ 作为倍增分块的参数，$14$ 是常数较小的，因为每个数字的变块次数和块数变少，大大减少了时空常数。
可以用 $40$ 作为底层分块的参数，这时可以稳过。
总时间复杂度 $O(n\log_2n\log_2V)$，空间 $O(n)$。