[XJB研究] [分块] 关于分块时间复杂度的证明

如果你知道分块的时间复杂度是O(n√)$O(/sqrt n)$，请忽略这篇博文。 如果你并不关心是怎么证明出来的，请忽略这篇博文。 如果你是神犇，请务必忽略这篇博文。 以下证明又是在数学课上瞎想，如果有误欢迎提出…… （数学老师我错了......） 1、规定符号 n$n$：序列的长度； S$S$：将这个序列分成S$S$块； C$C$：分成的每个块内有C$C$个元素； x$x$：查询或修改时，需要操作的整块数； y$y$：查询或修改时，需要操作的零散区间中元素个数； L$L$：查询或修改时，操作序列的长度。 通过符号规定，可以看出一定有：SC=n，x≤S，y<2C$SC=n，x≤S，y<2C$。 2、目的 通过分块，统一维护块内元素，查询时可以快速取出整块内答案，再与零散区间合并，达到降低时间复杂度的目的。（这种元素需满足区间加法维护的性质）。 因此，需要最小化修改与查询次数。即最小化x+y$x+y$的值。 3、证明 ① 当最差情况下时，操作的区间为[2,n−1]$[2,n-1]$，此时需要查询S−2$S-2$个块和2C−2$2C-2$个元素，即x=S−2,y=2C−2$x=S-2,y=2C-2$。 x+y=S−2+2C−2=S+2C−4$x+y=S-2+2C-2=S+2C-4$。忽略常数，得x+y=S+C$x+y=S+C$。 因SC=n$SC=n$，则C=nS$C=/frac {n}{S}$。 代入，得 x+y=S+nS≥2∗S∗nS−−−−−√=2n√$x+y=S+/frac{n}{S}≥2*/sqrt {S*/frac{n}{S}}=2/sqrt n$ 当且仅当S=nS$S=/frac{n}{S}$，即S=n√$S=/sqrt n$时，等号成立。 所以在最坏时，时间复杂度为O(n√)$O(/sqrt n)$。常数不超过3$3$。 ② 在一般情况下时，可以得出L=xC+y$L=xC+y$。 移项，得x=L−yC$x=/frac{L-y}{C}$。 因0<L≤n,0<y<2C$0<L≤n,0<y<2C$，则0<L−y<n−2C$0<L-y<n-2C$。 因C>0$C>0$，则L−yC<n−2CC=SC−2CC=S−2<S$/frac{L-y}{C}</frac{n-2C}{C}=/frac{SC-2C}{C}=S-2<S$ 故x+y<S+2C$x+y<S+2C$，忽略常数，x+y<S+C$x+y<S+C$。 因SC=n$SC=n$，S+C≥2SC−−−√=2n√$S+C≥2/sqrt{SC}=2/sqrt n$。 当且仅当S=C$S=C$，即S=C=n√$S=C=/sqrt n$时，等号成立。 此时x+y<2n√$x+y<2/sqrt n$。 综上，分块的时间复杂度为O(n√)$O(/sqrt n)$，常数不超过3$3$。证毕。 分块中，S与C的取值可以任意，只是当S=C=n√$S=C=/sqrt n$时，时间复杂度最优。在有些JOI题目中（如[BZOJ4241] 历史研究）使用的S$S$和C$C$不是最优的，但是也可以A掉这种题。