【算法】浅谈数列分块问题 – Sora1336

写这篇博文呢，主要还是为了准备信息队员交流，毕竟分块是我最喜欢的数据结构，所以我就试着写了一篇博文。

---

基本介绍：

分块是维护较为复杂的信息的，尤其是不满足区间可加性可减性的信息的重要工具。如果运用树状数组或线段树，代码也非常的麻烦和不直观，Debug 可以 Debug 一天。而分块是以一种 “暴力” 的思想来维护信息的，所以非常直观和好理解。其基本思想就是通过把序列划分为多个小块（块长一般为 $\sqrt n$）并预处理出一部分信息保存下来，从而达到维护信息的一种数据结构。分块直观，通用，容易理解和实现。接下来我将以几道例题来谈谈分块。

[Example 1] A Simple Problem with Integers

给定长度为 $N(N\le 10^5)$ 的数列 $A$ ， 然后输入 $Q(Q\le 10^5)$ 行指令。

第一类指令形如 C l r d ，表示把数列中第 $l\sim r$ 个数都加 $d$.

第二类指令形如 Q l r ，表示询问数列中第 $l\sim r$ 个数的和.

固然，这道题可以使用树状数组或线段树在 $O((n+m)\log n)$ 的时间复杂度内解决此问题，但是我们现在使用分块来求解。

我们考虑把数列 $A$ 分解成 $N$ 个长度为 $\lfloor \sqrt N\rfloor$ 的段，其中第 $i$ 段左端点为 $(i-1)\lfloor \sqrt N\rfloor + 1$ ，右端点为 $\min(i\lfloor \sqrt N\rfloor,N)$ ，如图所示（大约很丑）。

像这样，我们把一个数列分成了 $\sqrt n$ 段。

我们可以预处理出每段的数字之和，存在数组 $sum$ 里面，其中 $sum_i$ 便是第 $i$ 段的区间和，最后另外开一个 $add$ 数组，然后设 $add_i$ 为这个块上还要加的数，起初 $add_i=0$ 。

我们分别进行处理：

1. 区间加指令。

• 如果 $l$ 和 $r$ 在同一块 $i$ 里面，暴力修改，把 $A_l,A_{l+1}···A_r$ 都加 $d$ 的同时 $sum_i+=d(r-l+1)$ 。

• 要不然就让 $l$ 在第 $lb$（Left Block）段，让 $r$ 在第 $rb$（Right Block）段。首先对于 $i \in [lb+1,rb-1]$ ，使 $add_i+=d$ 。然后两端朴素更新。

2. 区间查询指令。

• 如果 $l$ 和 $r$ 在同一块 $i$ 里面，暴力查询，答案是 $\sum\limits^{r}_{i=l}a_i+add_i(r-l+1)$ 。

• 要不然就让 $l$ 在第 $lb$（Left Block）段，让 $r$ 在第 $rb$（Right Block）段。首先对于 $i \in [lb+1,rb-1]$ ，使 $ans+=sum_i+add_i\times len_i$（$len_i$ 表示第 $i$ 块的块长）。然后两端朴素查询。

这就是分块算法的基础——对 $add$ 数组的使用。以后可能会用更多的数组来维护一个分块，我们统称其为 “大分块”。不过目前的阶段没有必要碰这个毒瘤的玩意。

因为段数和块长都是 $\sqrt n$ ，所以整个算法的时间复杂度为 $O((n+m)\sqrt n)$ 。

typedef long long ll;
ll a[100010], sum[20010], add[20010];
int L[20010], R[20010];      //左右端点
int pos[100010];             //每个位置属于哪一段
int n, m, t;
void change(int l, int r, long long d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++) a[i] += d;
        sum[p] += d*(r - l + 1);
    }else {
        for (int i = p + 1; i <= q - 1; i++) add[i] += d;
        for (int i = l; i <= R[p]; i++) a[i] += d;
        sum[p] += d*(R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) a[i] += d;
        sum[q] += d*(r - L[q] + 1);
    }
}
ll ask(int l, int r) {
    int p = pos[l], q = pos[r];
    long long ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++) ans += a[i];
        ans += add[p] * (r - l + 1);
    }else {
        for (int i = p + 1; i <= q - 1; i++)ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; i++) ans += a[i];
        ans += add[p] * (R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    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];
    while (m--) {
        char op[3];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if (op[0] == 'C') {
            scanf("%d", &d);
            change(l, r, d);
        }else printf("%lld\n", ask(l, r));
    }
}

呃，这个，大家都知道我是 $\log$ 分块邪教的 (/ω＼) 这样的块长是 $\log(n)\times 5$ 最坏时间复杂度是 $O((n+m)\frac{n}{\log n\times5})$ ，在 $Q$ 多的数据下效率非常不错（DarkBZOJ Top1）, 但是对于 $n$ 多的数据就会非常坑爹。

请完成例题的代码实现：

• loj6280 数列分块入门 4

请独立思考完成以下习题：

• loj6277 数列分块入门 1
• loj6279 数列分块入门 3
• loj6283 数列分块入门 7

---

[Example 2] 教主的魔法

给定长度为 $N(N\le 10^6)$ 的数列 $A$ ， 然后输入 $Q(Q\le 3\times 10^3)$ 行指令。

第一类指令形如 M l r d ，表示把数列中第 $l\sim r$ 个数都加 $d$.

第二类指令形如 A l r k ，表示在区间 $l\sim r$ 求大于等于 $k$ 的数的个数.

修改操作在前面已经说过了，大区间打标记，小边角暴力改，最后区间要查询的就是 $k-add_i$，修改时直接排序。

我们再来考虑询问操作，直接把查询的块排好序，然后二分查找 $k$ 的值，最后边角料直接暴力检查是不是大于等于 $k$ 。

然后就可以过了。注意单块查询的时候考虑 $add$ 数组的值。

复杂度大约是 $O(n\log n +m\sqrt{n \log n})$。

其实代码实现还是挺简单的。

#define fir(a, b, c) for(register int a = b; a <= c; a ++)
int n, q, a[N], b[N], l[N], r[N], pos[N];
int t, tag[N];
inline int ask(int x, int y, int k){
    int ans = 0;
    if(pos[x] == pos[y]){
        fir(i, x, y)
            if(a[i] + tag[pos[x]] >= k) ans ++;
        return ans;
    }
    fir(i, x, r[pos[x]])
        if(a[i] + tag[pos[x]] >= k) ans ++;
    fir(i, l[pos[y]], y)
        if(a[i] + tag[pos[y]] >= k) ans ++;
    fir(i, pos[x]+1, pos[y]-1){
        int p = lower_bound(b+l[i], b+r[i]+1, k-tag[i])-b;
        ans += r[i]-p+1;
    }
    return ans;
}
inline void change(int x, int y, int k){
    if(pos[x] == pos[y]){
        fir(i, x, y) a[i] += k;
        fir(i, l[pos[x]], r[pos[x]]) b[i] = a[i];
        sort(b+l[pos[x]], b+r[pos[x]]+1);
    }else{
            fir(i, x, r[pos[x]]) a[i] += k;
            fir(i, l[pos[x]], r[pos[x]]) b[i] = a[i];
            sort(b+l[pos[x]], b+r[pos[x]]+1);
            fir(i, l[pos[y]], y) a[i] += k;
            fir(i, l[pos[y]], r[pos[y]]) b[i] = a[i];
            sort(b+l[pos[y]], b+r[pos[y]]+1);
        fir(i, pos[x]+1, pos[y]-1) tag[i] += k;
    }
}
int main(){
    scanf("%d %d", &n, &q);
    fir(i, 1, n) scanf("%d", &a[i]), b[i] = a[i];
    t = sqrt(n);
    fir(i, 1, t) l[i] = (i-1)*t+1, r[i] = i*t;
    if(r[t]<n) t ++, l[t] = r[t-1]+1, r[t] = n;
    t = 1;
    fir(i, 1, n)
        if(i > r[t]) t ++, pos[i] = t;
        else pos[i] = t;
    fir(i, 1, t) sort(b+l[i], b+r[i]+1);
    char opt;int x, y,z;
    while(q --){
        cin>>opt; 
        scanf("%d %d %d", &x, &y, &z);
        if(opt == 'A') printf("%d\n", ask(x, y, z));
        else change(x, y, z);
    }
}

好吧其实要注意的地方还挺多的… 当时是调了一个晚上差不多。

请完成例题的代码实现：

• P2801 教主的魔法

请独立思考完成以下习题：

• loj6278 数列分块入门 2
• loj6279 数列分块入门 3

[Example 3] 蒲公英

给你一个长度为 $n$ 的数列 $a$ ，有 $m$ 次询问，每次询问一个区间 $l\sim r$ ，求该区间的区间众数。如果众数有多个，则输出最小的那一个。注意，你的算法必须是在线的。

考虑 $O(n\sqrt{n\log n})$ 做法：预处理所有以段边界为端点的区间 $[l,r]$ 的众数，再对每个数字建一个 vector 桶，按顺序保存该数值在序列 $a$ 中每次出现的位置。

对于每个询问，扫描 $[l,L)$ ，$(R,r]$ 中每个数 $x$ ，在对应的 vector 里二分查找即可得到答案。

const int maxn=1e5+5;
typedef long long ll;
int size,belong[maxn];
int f[505][505];int cnt[maxn];
vector<int>s[maxn],v;
int n,m;
int val[maxn];
int ans;
int a[maxn];
inline void prework(int x){
    memset(cnt,0,sizeof(cnt));int mx=0,ans=0;
    for(int i=(x-1)*size+1;i<=n;i++){
        cnt[a[i]]++;
        if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&val[a[i]]<val[ans]))ans=a[i],mx=cnt[a[i]];
        f[x][belong[i]]=ans;
    }
}
inline int find(int l,int r,int x){
    return (int)(upper_bound(s[x].begin(),s[x].end(),r)-lower_bound(s[x].begin(),s[x].end(),l));
}
inline int query(int l,int r){
    int ans=f[belong[l]+1][belong[r]-1],mx=find(l,r,ans);
    for(int i=l;i<=min(belong[l]*size,r);i++){
        int t=find(l,r,a[i]);
        if(t>mx||(t==mx&&val[a[i]]<val[ans]))mx=t,ans=a[i];
    }if(belong[l]!=belong[r]){
        for(int i=(belong[r]-1)*size+1;i<=r;i++){
            int t=find(l,r,a[i]); 
            if(t>mx||(t==mx&&val[a[i]]<val[ans]))mx=t,ans=a[i];
        }  
    }return ans;
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
inline void print(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read();
    m=read();
    v.push_back(-1);
    size=sqrt(n);
    for(int i=1;i<=n;i++)a[i]=read(),v.push_back(a[i]);
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++){
        int b=a[i];
        a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        val[a[i]]=b;
    }for(int i=1;i<=n;i++)s[a[i]].push_back(i);
    for(int i=1;i<=n;i++)belong[i]=(i-1)/size+1;
    for(int i=1;i<=belong[n];i++)prework(i);
    for(int i=1;i<=m;i++){
        int l,r;l=read();r=read();
        l=(l+ans-1)%n+1;r=(r+ans-1)%n+1;
        if(l>r) swap(l,r);
        print(ans=val[query(l,r)]);
        putchar('\n');
    }
}

感谢 Bovine__Kebi 提供的 $O(n\sqrt{n\log n})$ 代码。

请完成例题的代码实现:

• P4168 [Violet] 蒲公英

请独立思考完成以下习题：

• loj6285 数列分块入门 9
• loj6285 数列分块入门 8

---

我们现在分块的学习可以入门了。（也许我可以搞个进阶教程）我们掌握了分块的思想和基本操作，那么非常感谢您能阅读到这里！！！谢谢 qwq

如有谬误，敬请指正 qwq