块状数组

· · 个人记录

分块是一种 思想 ，简洁的来说，就是把一个整体划分为若干个小块，对整块 整体 处理，零散块 单独（暴力） 处理。

块状数组

但花花这里所要介绍的是一种基于分块思想的数据结构 —— 块状数组

首先对于提高以及低难度省选的区间问题，可以用线段树、树状数组等数据结构及其拓展以更优的复杂度进行解决，但都有些许劣势，例如线段树的空间过大，树状数组的适用范围小。

那是否有一种处于平衡点的数据结构呢？

块状数组是一种处理区间问题根号数据结构，对于大多数不卡根号的题目，是可以卡常通过的。

优点：通用性强，空间复杂度低，易实现（码量与线段树差不多）。

缺点：较基于分治思想的数据结构如线段树、平衡树等效率较低，仅能做到 \mathcal{O} (n \sqrt{n} ) 的时间复杂度。

先对一些名词做一些解释：

区间 ：数列中连续一段的元素。

区间操作 ： 将一个区间 [l,r] 的所有元素进行一种操作。

块 ： 把一个数列分成若干个不相交的区间，每个区间称为一个块。

整块 ： 在一个区间操作中，完整包含于区间的块。

不完整的块 ： 在一个区间操作中，除整块意外的散块，即区间两个端点所在的两个块。

块状数组把一个长度为 n 的序列分成 x 块，每一块的长度为 \frac{n}{a} 。对于一个区间操作，整块直接处理，散块暴力处理。

显然分的块数会极大的影响时间复杂度，根据一半不等式，可以得出当块长度为 \sqrt{n} 时可以达到最小值，故通常使用 \sqrt{n} 块可以达到最优复杂度（具体题目具体分析）出题人恶意针对除外 ，总复杂度大致为 \mathcal{O}(\sqrt{n})

花花的叙述能力较差，所以后面我们结合代码来讲解。

预处理

ll n,a[1000005];
ll block,cnt;
ll L[1105],R[1105],belong[1000005];

这里的 block 是块的大小， cnt 是块的数量， L_i,R_i 指的是第 i 个块的左右端点， belong_i 指的是第 i 个元素所属的块。

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

这里确认了块的大小以及数量，因为 n 不一定为完全平方数，所以需要判断是否有不完整的块，如果有，块数加 1 。

for(int i=1;i<=n;++i){
    belong[i] = (i-1)/block+1;
}
for(int i=1;i<=cnt;++i){
    L[i] = (i-1)*block+1;
    R[i] = i*block;
}
R[cnt] = n;

因为每个块的大小为 block 所以对第 i 个数所属的块即为 \frac{i-1}{block} +1 ，同理，反过来就可以退出每个块的左端点和右端点，最后因为不保证没有不完整的块，所以最后一个块的右端点需要设为 n 。

以上就是基本的初始化建块操作，不同的题目需要对其进行相应的变化。

现在我们来通过一道例题实操一下 P3372 【模板】线段树 1

简要题意：维护一个长度为 n 的序列，需支持区间加法和区间和的查询。

思路：对于加法，如果 l 和 r 在同一个块中,那么对于这个区间每个数增加 k ，加权和也增加区间的元素数量\times k（暴力求解），同理对于两旁可能出现的不完整的块要进行端点的伸缩来进行同样的操作，对于整块，只需要对 lazy 标记增加，块的和增加 block\times k 。

对于查询操作，如果在同一个块中就进行暴力查询，否则对整块的和进行相加对不完整的块暴力处理。

拓展：P3373 【模板】线段树 2 与线段树 1 不同的是多了个乘法操作，所以对于 lazy 标记要做到先乘后加。

P2801 教主的魔法

简要题意：维护一个长度为 n 的序列，需支持区间加法区间和查询区间有多少个元素大于等于 k 。

思路：与前面的区间加法类似，我们对于区间加法操作会在此基础上加上一个排序同时将数组进行复制，至于作用在查询的时候会讲。

void add(ll nowl,ll nowr,ll addk){
    if(belong[nowl]==belong[nowr]){   //在同一块 
        for(int i=nowl;i<=nowr;++i){
            a[i]+=addk;
        } 
        for(int i=L[belong[nowl]];i<=R[belong[nowr]];++i){
            b[i] = a[i];
        }
        sort(b+L[belong[nowl]],b+R[belong[nowl]]+1);
    }
    else{   //不同块 
        for(int i=nowl;i<=R[belong[nowl]];++i){   //左开 
            a[i]+=addk; 
        }
        for(int i=L[belong[nowl]];i<=R[belong[nowl]];++i){
            b[i] = a[i];
        }
        sort(b+L[belong[nowl]],b+R[belong[nowl]]+1);
        for(int i=L[belong[nowr]];i<=nowr;++i){   //右开 
            a[i]+=addk; 
        }
        for(int i=L[belong[nowr]];i<=R[belong[nowr]];++i){
            b[i] = a[i];
        }
        sort(b+L[belong[nowr]],b+R[belong[nowr]]+1);
        for(int i=belong[nowl]+1;i<=belong[nowr]-1;++i){
            lazy[i]+=k;
        }
    }
}

首先对于整块来讲，我们所查询的内容和顺序无关，散块的话我们不能改变原序列，这时复制的数组就有用了，我们可以在那上面进行操作和查询，因为已经对整块排好序了，所以直接二分查找第一个大于等于 k 的数，那后面的就可以加减求出是否满足，散块排序后同样进行处理。

ll solve(ll nowl,ll nowr,ll check){
    ll res = 0;
    if(belong[nowl]==belong[nowr]){
        for(int i=nowl;i<=nowr;++i){
            if(lazy[belong[nowl]]+a[i]>=check){
                ++res;
            }
        }
        return res;
    }
    else{
        for(int i=nowl;i<=R[belong[nowl]];++i){
            if(lazy[belong[nowl]]+a[i]>=check){
                ++res;
            }
        }
        for(int i=L[belong[nowr]];i<=nowr;++i){
            if(lazy[belong[nowr]]+a[i]>=check){
                ++res;
            }
        }
        for(ll i=belong[nowl]+1;i<=belong[nowr]-1;++i){
            res+=binary_search(i,check);
        }
        return res;
    }
}

当然如果还按前面那样的建块是过不去的，所以我们在建块时要复制数组，并将其复制的数组按块排序一下。

这样这道题的时间复杂度就可以做到 \mathcal{O} (m \sqrt{n log_2 n}) ，可以轻松操过这道题。

P3203 [HNOI2010]弹飞绵羊

简要题意：给 n 个点，这个点可以跳到 i+k_i 的地方，支持修改 k_i和查询一个点要跳多少次才能跳出。

思路：虽然这是一道省选紫题，但如果好好想想会发现这只是个单点修改单点查询的题目，所以建块以后只需要维护两个值： step_i 表示第 i 个点弹出所需次数， lazy_i 表示这个点落到其他块的点。

所以对于查询，我们从起点出发，用 lazy 查询下一个点，累加 step 大于 n 即完成，因为最多每个块跳一遍过去，所以时间复杂度是 \mathcal{O}(\sqrt{n}) 。

ll solve(ll che){
    ll res = 0;
    while(che<=n){
        res+=step[che];
        che = lazy[che];
    }
    return res;
}

对于修改，发现 step_i 和 lazy_i 只和所在的块有关，所以对于单点修改只需根据查询所需维护单块，时间复杂度为 \mathcal{O} (\sqrt{n}) 。

void add(ll x,ll y){
    a[x] = y,flag = belong[x];
    for(int i=R[flag];i>=L[flag];--i){   //清除操作
        step[i] = 0;
        lazy[i] = 0;
    }
    for(int i=R[flag];i>=L[flag];--i){
        if(a[i]+i>R[flag]){
            step[i] = 1;
            lazy[i] = a[i]+i;
        }
        else{
            step[i]+=step[a[i]+i]+1;
            lazy[i] = lazy[a[i]+i];
        }
    }
}

这样一道正解为 LCT 的题就可以卡常过。

综上块状数组是一种好想且易编写的数据结构，对于区间问题，且序列长度和操作数在 10^5 \sim 10^6 的问题就可以思考是否能使用块状数组进行解决。