【笔记】序列分块

介绍

定义:就是把一段序列分成一小块一小块得来处理,维护

我们把一段当成一个整体,只记录维护整体的有关信息,就是分块。

块状数组可被看成一棵高度为\(3\)的树。(块状数组最顶层的信息不用维护)
线段树可被看成一颗高度为 \(log\;n\) 的树。

分块就是在暴力的基础上进行优化 —— 某人名言

将原序列长度为\(n\)的快切成 \(\sqrt n\) 块。

定义两个东西:

完整块:被操作区间完全覆盖的块

不完整块:操作区间不完全覆盖的块

对于完整块查询直接查就好了,对于不完整块查询一般用暴力(长度为\(\sqrt n\)) ,或者用二分,倍增来优化。

对于完整块修改可以用懒标记或差分等方法来优化,对不完整块可以暴力。

建块

具体地使用块状数组,我们要先划定出每个块所占据的范围:

int sqrtn = sqrt(n);//块数
for (int i = 1; i <= sqrtn; i++)
{
    start[i] = n / sqrtn * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
    end[i] = n / sqrtn * i; // ed[i]表示i号块的最后一个元素的下标
}

但是,数组的长度并不一定是一个完全平方数,所以这样下来很可能会漏掉一小块,我们把它们纳入最后一块中:

end[sqrtn] = n;

然后,我们为每个元素确定它所归属的块:

for (int i = 1; i <= sqrtn; i++)
    for (int j = start[i]; j <= end[i]; ++j)
        belong[j] = i; // 表示j号元素归属于i块

最后,如果必要,我们再预处理每个块的大小:

for (int i = 1; i <= sqrtn; i++)
    size[i] = end[i] - start[i] + 1;

这样,块状数组的初始化就完成了。

上一篇:【数据结构】分块(2/8)希望能抓到8月份的小尾巴


下一篇:根号算法学习笔记