神金的多层分块

· · 算法·理论

在一些场景下，我们常常会遇到修改与查询次数极不相等的情况（如 O(n) 次修改 O(n\log n) 次查询或者反过来）。如果使用平凡的 O(\operatorname{poly}(\log)) 的 ds 维护，那么时间复杂都往往不可接受（如 n=10^6,O(n\log^3n) 或者 n=10^5,O(n^{\frac32}\log n)）。

那么这个时候，某些奶龙可能会想到使用分块维护。但是这样的复杂度是 O(\sqrt{n})，更劣。有些聪明的奶龙可能会想到对于某些操作，可以做到 O(\sqrt{n})-O(1) 或者 O(1)-O(\sqrt{n})，那么使用 O(1) 维护数量级较大的操作，用 O(\sqrt{n}) 维护数量级较小的操作。这样可以把复杂度降为 O(m+n^{\frac32})(m>>n)。

典型的例子是莫队二离，例题一大堆，自己找。

但有时这样还不够，尤其是当你获得这个复杂度的时候一看 n=10^6。这时候我们充分发扬奶龙智慧，考虑二层分块，那么复杂度变为 O(1)-O(n^{\frac13})。这个时候复杂度为 O(m+n^{\frac43})(m>>n)，即使是 10^6 也绰绰有余。当 n=10^5 时，\log n=17,n^{\frac13}=45，基本可以当大常数 n\log n 用。例题一大堆，自己找。

当然你也可以尝试三层分块或者更多，复杂度 O(n^{\frac1k})-O(k)，\log n 层分块就是线段树。例题 P3372。