第二分块没改出来给我干破防了。提交记录：五彩斑斓的世界（）。
分块的种类
- 序列分块：本质是在下标轴（\(i\)）上分块。
- 值域分块：本质是在值的轴（\(a_i\)）上分块。
- 操作分块：本质是在时间轴（一般是输入顺序）上分块。
这几种分块应该是可以套的。
分块、莫队、根号分治的核心
平衡。
- 平衡整块和散块的[时间]（？）复杂度。（分块）
- 平衡修改和查询的[时间]（？）复杂度。（分块）
- 如 单点加，区间求和：
分块维护原序列（直接做）：\(O(1)\) 修改，\(O(\sqrt n)\) 查询。
分块维护前缀和（整块维护整个序列的前缀和，散块维护块内的前缀和）：\(O(\sqrt n)\) 修改，\(O(1)\) 查询。
- 如 单点加，区间求和：
- 平衡预处理和[操作]（？）的[时间]（？）复杂度。（在线莫队）
- 平衡两种情况的[时间]（？）复杂度。（根号分治）
目前想到了这些。
标签：前缀,分块,复杂度,链表,平衡,莫队,根号 From： https://www.cnblogs.com/huangkxQwQ/p/18377423分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。—— August 22, 2024 cyf 老师的 ppt