分块初步学习

例题：区间加，区间查询

下文使用 \(m\) 表示查询次数，以示区分。
朴素做法 \(O(m\times n)\).
我们发现需要优化后面这个 \(n\).
考虑分块。将整个区间打成 \(\lceil n / \sqrt{n} \rceil\) 块。
称有 \(\sqrt{n}\) 个数于其中的块为 整块，反之则称为 散块。
对于区间加，令区间为 \([l,r]\).
当 \(l,r\) 位于同一个块时，暴力处理。复杂度 \(O(\sqrt{n})\).
否则：令 \(l\) 位于第 \(p\) 个块，\(r\) 位于第 \(q\) 个块。从第 \((p+1)\) 个块到第 \((r-1)\) 个块，将它们视为整体，仅需要打上标记即可。在第 \(p\) 个块和第 \(q\) 个块再暴力处理。复杂度 \(O(3\sqrt{n})=O(\sqrt{n})\).
查询操作也与之类似。总复杂度 \(O(m\sqrt{n})\).

分块初步学习

原文：https://www.cnblogs.com/Xray-luogu/p/14227555.html