分块不仅算是一种数据结构，也算是一种思想，一般用均值不等式求出最优值，一般带根号
\(\log\) 下面即根号，想不出别的数据结构维护方法，就想根号！
数论分块
求 \(\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor\)，这玩意数量级为 \(O(n\log n)\)
将 \(1\sim n\) 分成若干个块，对于 \(i\)，块的右端点为 \(\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\rfloor\)
for(int l=1,r;l<=n;l=r+1) {r=n/(n/l);ans+=(r-l+1)*(n/l);
}
区间数（不同值种类）为 \(O(\sqrt n)\)
数论上的分块思想总伴随的倍数，值域极大
AT_arc068_c [ARC068E] Snuke Line
考虑对于一个区间 \([l_i,r_i]\)，如果存在 \(x\) 满足 \(l_i\le d\times x\le r_i\)，那么这个区间对 \(d\) 有贡献，即如果存在 \(\lfloor \frac{l_i-1}{d} \rfloor<x\le \lfloor\frac{r_i}{d}\rfloor\)，也就是如果 \(\lfloor \frac{l_i-1}{d} \rfloor < \lfloor\frac{r_i}{d}\rfloor\)，那么这个区间对 \(d\)
上面是一维数论分块，扩展到二维分块，即对于 \(n_1,n_2\)，将 pair\((\lfloor\frac{n_1}{i}\rfloor,\lfloor\frac{n_2}{i}\rfloor)\) 相同的 \(i\) 分在一块，容易知道块的数量为 \(O(\sqrt n)\)
对于每一块，如果满足上述条件，那么此区间就对这一块的 \(d\) 有贡献，这个贡献可以通过差分统计
for(int l=1,r1,r2,r;l<=x;l=r+1) {r1=x/(x/l);r2=y/(y/l);r=min(r1,r2);if(x/l<y/l) ++d[l],--d[r+1];
}
根号分治
根号分治和数据结构中的分块并不能混为一谈，根号分治更是一种思想，将不同的暴力（\(O(B),O(\frac{n}{B})\) ）的优势拼在一起，从而达到一个平衡下复杂度不错的东西。
洛谷P8250 交友问题
先想一想暴力：
-
直接枚举 \(u\) 的所有出边，并判断这些出边和 \(v\) 的出边有多少重复的
直觉上如果 \(u\) 的出边比较少，再用一个 \(\log\) 就可以判断了
-
如果 \(u\) 的出边很多，枚举就会达到 \(O(nq)\)，我们需要快速判断有多少人既是 \(u\) 的朋友也是 \(v\) 的朋友。用
b[u]&b[v]来表示就可以了，用bitset可以做到时空都是 \(O(\frac{n}{w})\)
时间是 1.2e9 空间 1e8
假设以 \(B\) 为分界，方法一的时间 \(O(n B\log n)\)，方法二时间\(O(\frac{n}{w})\)，空间为 \(O(\frac{n^2}{B})\)，让 \(B=\sqrt{\frac{n}{\log n}}\)，理论上要让 B 稍微大一点
ARC052D 9
\(10^{10}\) ，第一眼应该是数位 dp，比如设 \(f_{i,j,k,0/1}\)，当前考虑到第 \(i\) 数位，余数为 \(j\)，数位和为 \(k\)，是否顶到了最大的 \(M\)。
注意到数位和最大为 90，但是 \(j\) 也就是 \(K\) 可以很大。但是当 \(K\) 很大的，对于一个固定的数位和 \(i\)，只有 \(\frac{M}{k}\) 种，这个可能很小。
那么对 \(K\) 设定一个阈值，平衡后就可以做到根号了。
CF1039D You Are Given a Tree
首先对于一个固定的 \(k\) 暴力怎么求出答案，从子树开始遍历，只要能拼成 \(k\) 路径那么就拼，这样一定是最优的。那么就可以通过 \(O(n)\) 的 DP 来解决一个 \(k\)。
注意 \(k\) 的答案单调不减，那么可以考虑二分。
继续观察，\(k\) 越大，答案越密集，注意到当 \(k\ge \sqrt n\) 时，\(ans\le \sqrt n\) ，如果枚举的是答案，然后二分出答案区间即可。
复杂度可以做到 \(O(n\sqrt{n\log n})\)
块状数组
更偏向于一种数据结构。将一个数组分为几个块，块内信息整体维护，查询时的散点暴力查询。
P2801 教主的魔法
开一个新的数组 \(t\)，维护每一个块顺序，这样查找的时候每一个块一个 \(\log\) ，总复杂度为 \(O(q\log n\sqrt n)\)
P5356 [Ynoi Easy Round 2017] 由乃打扑克
动态区间第 \(k\) 小，事实上区间第 \(k\) 大的数可以通过二分一个数，再判断这个数的排位，不断二分得到答案
对于此题也可以每个块维护有序，每次查询就二分一个数，然后每个块判断，复杂度 \(O(q\log V\log n \sqrt n)\)
块状链表
链表插入为 \(O(1)\)，但是查询为 \(O(n)\)，而数组相反，那么两者结合一下，维护若干个块，每个块是一个链表，当链表数量超过 \(2B\) 的时候就重构。
树分块
考虑能将树上任意路径都分成 \(\sqrt n\) 的方法，在树上撒 \(\sqrt n\) 的点，并保证这些点任意两个点的距离 \(\ge \sqrt n\)，具体操作如下：
void dfs1(int u,int f) {mxd[u]=dep[u]=dep[f]+1;for(int v : g[u]) {if(v==f) continue;dfs1(v,u);}if(mxd[u]-dep[u]>B) {mxd[u]=dep[u];id[u]=++tot;}
}
这样任意路径分为 \(\sqrt n\)，每一块我们都预处理，将路径看成序列来做就行了。
P6177 Count on a tree II/【模板】树分块