如果你知道分塊的時間復雜度是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掉這種題。