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[] - 数列中某数所在的区间下标