分块

简介

分块的关键在于把序列分为若干等长的块以及一个尾巴（或者分为若干不等长得块），把可以一起处理的问题放在一起处理。

根据均值不等式，块长取 \(\sqrt{n}\) 一般最佳。有些时候 \(n^{\frac{2}{3}}\) 是最优秀的，因题而异。这里忽略了常数，所以实际运用中可能可以把块长减小，俗称调块长。

一般的运用

一些需求复杂度很不平衡的题（如 \(O(1)-O(\log n)\) 或 \(O(\log n)-O(1)\) 复杂度。

一般的实现

泛用步骤：

• 同一块内，怎么处理
• 跨块怎么处理
  • 整块怎么处理
  • 块两端零散部分怎么处理

操作分块

就是把操作序列按时间分块。好处有：值域更小，可以标记永久化。

具体来说，操作分块之后，对于每个块，我们需要处理的值域、操作个数都变成了 \(\sqrt{n}\) 量级。这样，我们就可以做一个 \(O(值域\times 操作个数)\) 级别的计算。

具体一些，[P6578 Ynoi2019] 魔法少女网站 - 洛谷 中，对于每个操作块：建一个链表维护 \(>X\) 的点，\(X\) 表示从小到大枚举......

Sqrt Tree

shr版sqrt tree：

例题：单点修改，区间查询max（或者任何可结合量）。要求 \(O(\sqrt{n})\) 修改 \(O(1)\) 查询。

如果分块一下，我们希望在 块内数组 和 块间数组 做到 \(O(len)-O(1)\)，这不好做。我们再分块一下，我们希望做到 \(O(len^2)-O(1)\)，这就很简单了。

说白了，就是分块两次。（是不是还能继续分块，乐