当前位置: 首页 >资讯 > > 正文

分块，优雅的暴力

2023-07-31 18:07:45 来源：博客园

来看一下一个例题：

(资料图)

现在给出一个长度为 \(N\) 序列 A，定义两个操作如下：
1 l r v，表示从 \(A_l \sim A_r\) 每个数都加上 \(v\)。
2 l r，对 \(A_l \sim A_r\) 求和。

传统的线段树可以很优秀地实现这两个操作，但是需要打 \(lazytag\)。

同时因为线段树（非动态开点）的空间复杂度为 \(O(4N)\)，在空间限制或数据范围较大的题目中容易被卡，于是考虑用时间换空间，开发空间复杂度更优的算法。

分块就是这样的算法。

分块算法将整个序列分为若干个长度不超过 \(\sqrt n\) 的区间，并对于每个区间维护两个标记增量标记 \(add\) 和区间和 \(sum\)。其中增量标记 \(add\) 用来记录对于整个块的加法对答案产生的贡献，区间和 \(sum\) 用来记录整个区间内增量标记 \(add\) 之外的答案。

所以区间和查询就较为简单了。对于 \([l,r]\) 区间内的每个块，直接算 \(sum+add*(R_i-L_i+1)\) 计入答案即可，其中 \(L_i\) 和 \(R_i\) 分别表示第 \(i\) 个区间的左右端点。而对于区间两端不被整个分块覆盖的位置直接暴力统计即可。记 \(l,r\) 所在区间编号分别为 \(p,q\)，则两端的查询答案即为

\[\sum_{i=l}^{R_p}a_i+add_p\times(R_p-l+1)+\sum_{i=L_q}^{r}a_i+add_q\times(r-L_q+1)\]

于是将中间部分的答案和两端的答案直接合并就可以得到查询操作的答案了。

PS：如果 \(l,r\) 属于同一区间，则直接暴力统计即可。

inline int query(int l, int r) {    int res = 0, p = pos[l], q = pos[r];    if(p == q) {        for(int i = l; i <= r; i++) {            res += a[i] + add[i];        }        return res;    }    else {        for(int i = p + 1; i < q; i++) {            res += sum[i] + add[i] * (R[i] - L[i] + 1);        }        for(int i = l; i <= R[p]; i++) {            res += a[i];        }        res += add[p] * (R[p] - l + 1);        for(int i = L[q]; i <= r; i++) {            res += a[i];        }        res += add[q] * (r - L[q] + 1);        return res;    }}

如此暴力的做法复杂度是如何保证的呢？

观察到由于分块时每个区间长度均不超过 \(\sqrt N\)，于是中间统计部分最多不超过 \(\lceil \sqrt N \rceil\) 个区间，而两端暴力统计的次数总的不超过 \(2\sqrt N\)，所以整个查询的复杂度可以近似视作 \(O(\sqrt N)\)。

对于修改操作可以用相同的思想，每个完整区间直接加在增量标记 \(add\) 上，不完整区间则暴力往原序列 \(A_i\) 和区间和 \(sum\) 上加。总复杂度用相同的方法分析可以得到也为 \(O(\sqrt N)\)。

inline void change(int l, int r, int v) {    int p = pos[l], q = pos[r];    if(p == q) {        for(int i = l; i <= r; i++) {            a[i] += v;        }        sum[p] += (r - l + 1) * v;    }    else {        for(int i = p + 1; i < q; i++) {            add[i] += v;        }        for(int i = l; i <= R[p]; i++) {            a[i] += v;        }        sum[p] += (R[p] - l + 1) * v;        for(int i = L[q]; i <= r; i++) {            a[i] += v;        }        sum[q] += (r - L[q] + 1) * v;    }}

算法的预处理部分要处理的为每个区间的左右端点 \(L_i,R_i\)，每个位置 \(i\) 所对应的区间 \(pos_i\)，和原序列的区间和 \(sum_j\)，总复杂度为 \(O(N\sqrt N)\)

对于最后一个长度不满 \(\sqrt N\) 的区间直接处理即可。

t = sqrt(n);    for(int i = 1; i <= t; i++) {        L[i] = (i - 1) * sqrt(n) + 1;        R[i] = i * sqrt(n);    }    if(R[t] < n) {        t++;        L[t] = R[t - 1] + 1;        R[t] = n;    }    for(int i = 1; i <= t; i++) {        for(int j = L[i]; j <= R[i]; j++) {            pos[j] = i;            sum[i] += a[j];        }    }

若序列长度为 \(N\)，总操作数为 \(Q\)，则由上述分析可得分块算法的时间复杂度上界为 \(O((N+Q)\sqrt N)\)，空间复杂度为 \(O(N)\)。

在处理区间问题时，通常有树状数组、线段树和分块三种方法，三种方法各有优劣。