数列分块(数据结构)学习笔记

发现自己并没有掌握分块的正确姿势，然后于近期学习一下。

顺便提一下，分块是一个很好想，很暴力，复杂度较直接暴力比较低的算法

如果数据是随机数据那么实际复杂度会比期望要小。

然后最优分块的数目，根据不同的题目是不同的，可以通过均值不等式算出

但是大多数数据结构题目直接对数列进行$\sqrt{n}$的数列分块就可以了。

所以在下面的讨论中，我们假定所有数列分块按照最经典的$\sqrt{n}$的分块方式。

首先我们定义一些分块中普遍需要用到的东西即tr[1..num]结构体数组，其中全局变量num指的是分块的数目。

还有全局变量，block表示每一块元素的个数（除了最后一块）。

其中tr数组的类型div，含有三个元素l，r，val 分别表示块维护原数组左边界、右边界、维护该块的信息(可以适当添加描述这个块信息的参数，便于处理量询问)

首先，如果我们默认$\sqrt{n}$个元素作为一块，那么显然$block=\sqrt{n}$

如果$n$可以整除$block$，那么$num=\left \lfloor \frac{n}{block} \right \rfloor (block|n)$,否则$num=\left \lfloor \frac{n}{block} \right \rfloor+1 (block|n不成立)$

我们需要知道一个块处理是那个区间的信息,即tr[i].l,tr[i].r

那么还是给出公式： $tr_i.l=(i-1)\times block+1,tr_i.r=i\times block$ *特别的$tr_{num}.r=n$

然后我们还可能需要一个反映射，即原来数组中的哪个元素属于那个块。

那么我们可以修正一个公式$belong_i=\left \lfloor \frac{i-1}{block} \right \rfloor+1$

然后你可以预处理一些东西来维护这个块。

下面是预处理代码，

void build()
{
    block=sqrt(n); 
    num=n/block; if (n%block) num++;
    for (int i=1;i<=num;i++)
     tr[i].l=(i-1)*block+1,
     tr[i].r=i*block,
     tr[i].val=0;
    tr[num].r=n;
    for (int i=1;i<=n;i++)
     blong[i]=(i-1)/block+1;   
}

数列分块(数据结构)学习笔记

原文：https://www.cnblogs.com/ljc20020730/p/10486237.html