树状数组、线段树、ST 表……这些数据结构我们用的也不算少了，但实际上这些数据结构还不够灵活，面对一些区间问题时反而会出问题。
举个栗子：
现在有 \(n\) 个单调队列需要维护，将要进行 \(m\) 次操作，操作有两种：
1、给编号在 \([l,r]\) 的单调队列插入一个数字 \(x\)；
2、将编号为 \(x\) 的单调队列尾部的元素删除并插入编号为 \(y\) 的单调队列。
很显然，上述数据结构完全无法维护我提到的这个问题（虽然我接下来要说的思想也不一定能解决）。
所以，神通广大的 OIer 研究出了 分块 的思想。
分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。
而分块的时间复杂度则主要取决于块长，一般来说最优时间复杂度下的块长是可以通过下面的公式求出来的。
\[\sqrt[n]{\prod_{i=1}^n x_i}\le \frac{\sum_{i=1}^n x_i}{n} \]以上不等式取等号时，会满足 \(\prod_{i=1}^n x_i\) 最大或 \(\sum_{i=1}^n x_i\) 最小。
这就是 基本不等式（和高中课本上的不一样）。
但一般情况下，块长取 \(\sqrt n\) 就可以达到比较好的复杂度了。
分块思想非常灵活，下面讲一道例题。
给定长度为 \(n(1\le n\le 10^5)\) 序列 \(A\)，有两个操作：
1、令 \(A_l,A_{l+1},\cdots,A_r\) 加上 \(x\)；
2、求 \(\sum_{i=l}^r A_i\)。
我们将序列按每 \(s\) 个元素一块进行分块，并记录每块的区间和 \(b_i\)。
\[\underbrace{a_1, a_2, \ldots, a_s}_{b_1}, \underbrace{a_{s+1}, \ldots, a_{2 s}}_{b_2}, \ldots, \underbrace{a_{(s-1) \times s+1}, \ldots, a_n}_{b \frac{n}{s}} \]最后一个块可能是不完整的（因为 \(s\) 很可能不是 \(n\) 的倍数），但是这对于我们的讨论来说并没有太大影响。
首先看查询操作：
- 若 \(l\) 和 \(r\) 在同一个块内，直接暴力求和即可，因为块长为 \(s\)，因此最坏复杂度为 \(O(s)\)。
- 若 \(l\) 和 \(r\) 不在同一个块内，则答案由三部分组成：以 \(l\) 开头的不完整块，中间几个完整块，以 \(r\) 结尾的不完整块。对于不完整的块，仍然采用上面暴力计算的方法，对于完整块，则直接利用已经求出的 \(b_i\) 求和即可。这种情况下，最坏复杂度为 \(O(\frac{n}{s}+s)\)。
接下来是修改操作：
- 若 \(l\) 和 \(r\) 在同一个块内，直接暴力修改即可，因为块长为 \(s\)，因此最坏复杂度为 \(O(s)\)。
- 若 \(l\) 和 \(r\) 不在同一个块内，则需要修改三部分：以 \(l\) 开头的不完整块，中间几个完整块，以 \(r\) 结尾的不完整块。对于不完整的块，仍然是暴力修改每个元素的值（别忘了更新区间和 ），对于完整块，则直接修改 \(b_i\) 即可。这种情况下，最坏复杂度和仍然为 \(O(\frac{n}{s}+n)\)。
利用基本不等式可知，当 \(\frac{n}{s}=s\)，即 \(s=\sqrt{n}\) 时，单次操作的时间复杂度最优，为 \(O(\sqrt{n})\)。
标签：frac,分块,复杂度,完整,块长,ldots From： https://www.cnblogs.com/cantorsort2919/p/17042743.html