分块

Perface

“分块是优雅的暴力。”——卧野布值岛是水硕德·饭正狠堆

分块，是一种二次根号数据结构，虽然它的时间复杂度在大部分时候逊色于线段树，平衡树等对数数据结构，但它可维护信息的丰富性，较小的常数，线性的内存以及好写的代码使它在当今这个魔法般的神奇数据结构丛生的时代有了一席之地。

分块是少见的暴力数据结构，而且在另一个神奇的暴力数据结构——莫队中也有应用。

下文实现的是基础的数列分块。~~其他那些乱七八糟的 Spoon 也不会~~

Achieve

我们便用数列分块来做一下线段树模板一：区间修改 & 区间求和。

Build & Init

即建块，是最重要的部分。

你现在要把 N 个元素的数组划分成几个等长块，问块长 L 应当取多少呢？

令块数为 C .

显然有：

C * L = N

将 C , L 取最接近的，则：

L = sqrt(n)

注意要将 L 下取整。

但是你要问了：“那 N 不是完全平方数怎么办？最后一个块的块长不就不对了？？”

没事，就让最后一个块的块长不对好了，无伤大雅。

这便是最经典的根号分块，有时块长将做出玄学调整，如：sqrt(n) +or- 1……

来看一些定义：

fa[i] : 第 i 个元素所属的块的编号。

st[i] : 第 i 个块起始点在数组中的位置。

ed[i] : 第 i 个块终止点在数组中的位置。

sum[i]: 第 i 个块中所有元素之和。

lz[i] : 第 i 个块的懒标记。~~想不到吧，又是我~~

预处理：

都是推一推式子就得到的。

st[i] = n / L * (i - 1) + 1;

ed[i] = n / L * i

F(i, 1, L) {
    F(j, st[i], ed[i]) {
        fa[j] = i;
        sum[i] += a[j];
        lz[i] = 0; 
    }
}

特别地，由于上面那个无伤大雅的处理：

ed[L] = n

modify a Point

很简单，修改时先将点值修改，再把它的所属块的值修改。

void P(int i,int k) {
    sum[fa[i]] += k;
    a[i] += k;
}

Modify

这个东西就很神奇了。

假设要修改的区间为 [ ql , qr ] 。

若 fa[ql] == fa[qr] , 即他们在一个块里面，暴力遍历修改即可。

否则，先暴力修改两端的零散块，再整一块块地修改中间隔着的整块。

/* 将 [l , r] 加上 k */
void Mdf(int l,int r,int k) {
    if(fa[l] == fa[r]) {
        F(i, l, r) P(i,k); // 暴力修改每个点
    }
    else {
        F(i, l, ed[fa[l]]) P(i,k); // 暴力修改零散块
        F(i, st[fa[r]], r) P(i,k); // 同上
        F(i, fa[l] + 1, fa[r] - 1) lz[i] += k; // 直接修改懒标记
    }
} 

Query

和修改的思想相同，但要注意加上懒标记。

/* 求 [l, r] 的和 */
ll Qry(int l,int r) {
    ll res = 0;
    if(fa[l] == fa[r]) {
        F(i, l, r) res += a[i] + lz[fa[i]] ;  //暴力求和 别忘加懒标记 
    }
    else {
        F(i, l, ed[fa[l]]) res += a[i] + lz[fa[i]] ;    //同上
        F(i, st[fa[r]], r) res += a[i] + lz[fa[i]] ;    //同上
        F(i, fa[l] + 1, fa[r] - 1) res += sum[i] + lz[i] * (ed[i] - st[i] + 1);  // 块的懒标记要乘块长
    }
    return res;
}

Postscript

恭喜，你学会了一种极为灵活的数据结构！

更多神奇的操作要在切题中领悟。

#Perface

#Achieve

#Build & Init

#modify a Point

#Modify

#Query