“分块”算法的基本要素及 build() 函数的构建细节

【“分块”算法知识点】
● 分块是用线段树的分区思想改良的暴力法。代码比线段树简单。效率比普通暴力法高。分块适合求解 m=n=10^5 规模的问题，或 m*sqrt(n)≈10^7 的问题。其中，n 为元素个数，m 为操作次数。

● “分块”算法的基本要素
（1）块的大小用 block 表示。通常，令 block=sqrt(n)。其中，n 为元素个数。
（2）块的数量用 cnt 表示。计算块的数量的代码如下：

int block=sqrt(n);
int cnt=n/block;
if(n % block) cnt++;

（3）定义 pos[i] 为第 i 个元素所在的块。
若下标从 1 开始，则有 pos[i]=(i-1)/block+1。其中，block=sqrt(n)。
若下标从 0 开始，则有