分块
sLMxf
·
·
算法·理论
前置知识：求 S+\dfrac{n}{S} 的最小值，并求出 S。其中 n 是定值。
令 $x=S,y=\dfrac{n}{S}$，则有 $S+\dfrac{n}{S}\ge 2\sqrt{n}$。即 $S+\dfrac{n}{S}$ 的最小值为 $2\sqrt{n}$。
解方程，得到 $S=\sqrt{n}$。
### 1. 分块
分块将数组分成 $S=\sqrt{n}$ 块，每一次区间操作分成散块、整块操作。第 $i$ 块在第 $id_i=\dfrac{i}{n/S}+1$块。
他的修改时间复杂度为 $O(\sqrt n)$。
例如：开关
### 2. 分块例题1：[开关](https://www.luogu.com.cn/problem/P3870)
将其分为 $\sqrt n$ 块。$i$ 号点在 $id_i$ 块。
每一次修改，快速异或整块，暴力异或散块。
3. 推荐练习
- 线段树
- 弹飞绵羊