[洛谷日报第20期]浅谈基础根号算法——分块|_滚动_甘肃龙网

『甘肃龙网摘要_[洛谷日报第20期]浅谈基础根号算法——分块』小编提示您本文原始标题是：[洛谷日报第20期]浅谈基础根号算法——分块 a作者：刘浩...

小编提示您本文原始标题是：[洛谷日报第20期]浅谈基础根号算法——分块

a作者：刘浩宇（寂）

https://www.luogu.org/blog/48265/qian-tan-ji-chu-gen-hao-suan-fa-fen-kuai

----[洛谷日报第20期]浅谈基础根号算法——分块//----甘肃龙网 //

分块算法实质上是一种是通过分成多块后在每块上打标记以实现快速区间修改，区间查询的一种算法。其均摊时间复杂度为O(√n)

分块算法相较于各种树形数据结构，具有简便易写，方便调试等多种优点。在同等数据规模下，如1e5，其时间效率并不会低太多，在考试时反而是一种有力的得分方法。

接下来讲一下分块算法的基本操作及性质：

为了使得其有着最稳定的时间复杂度，我们经常讲一个长度为n的序列分为√n个大小为√n的块，如果n不是完全平方数，则序列最右端会多出一个角块

如下图，就是一种序列的分块：

----[洛谷日报第20期]浅谈基础根号算法——分块//----甘肃龙网 //

该长度为10的序列被分为了4块，前三块的大小为√10的近似值3，最后一个角块大小为1

而我们要记录的一个值，就是每个序号代表的数，属于哪一块

如上图，1,2,3就属于第一块，4,5,6就属于第二块，7,8,9就属于第三块，10就属于第四块

可以得到获取每一个序号的所在块的代码是：

----[洛谷日报第20期]浅谈基础根号算法——分块//----甘肃龙网 //

[洛谷日报第20期]浅谈基础根号算法——分块