Get 新专题 —— 分块
来和大家分享一下
其实这是以前讲过的 …… 我没认真听 …… 当初温习算是明确了 ……
注释局部
分块板子题 – LOJ 6277 数列分块入门 1
挂上链接 – https://loj.ac/problem/6277
题面很简略 – 数列的区间加法，单点查值
然而 …… 数列长度，操作数量最大可达 50000，单点查值问题不大，可区间加法就太坑了，如果硬做，工夫复杂度可达 O(n^2)，必定超时 ……
家喻户晓，操作越宏观复杂度越低。不难发现，区间加法一个一个加太过宏观，要设法往宏观拔。分块就是一种办法。
顾名思义，分块就是把数列分成若干块。怎么分呢？设块数为 a，一块数量为 b，总量为 n。咱们心愿 a 与 b 绝对均衡（起因一会就会明了）。依据 a 与 b 的数量关系，即 a *b=n，为使其均衡，无妨令 a，b 都为 sqnrt(n)(根号 n)。
分完块后就能够开始操作了
先来了解一下分块。分块的精华，即 ” 大段保护，小段奢侈 ”。大段即整段，也就是一个分块，小段即操作区间两端不满一块的局部。保护即整段操作，奢侈即原始的一个数一个数的操作。
对于这题，区间加法就能够使用 ” 大段保护，小段奢侈 ”。将操作区间分为 ” 大段 ”，” 小段 ”。
“ 大段 ” 操作，扫描每一个 ” 大段 ”，加到一个数中，将加一个一个加化为整体加，将宏观化为宏观。
“ 小段 ” 个别有两段，即左端和右端，别离一个数一个数的加
因为大段数量不会超过 sqrt(n)，小段中的数的总数也不会超过 2 sqrt(n)，所以区间加法的总复杂度从 O(n^2)级别降到了 O(n sqrt(n))级别
单点查问中单点的值 = 其独自的值 + 所在区间的对立加的值
那么，分块 1 到这就根本完结啦，上面会附上残缺代码 (C++) 和变量解释
残缺代码：
变量解释：
a[] – 数列
atag[] – 区间加值
p[] – 数列中某数所在的区间下标