介绍

分块的基本思想是通过适当的划分和预处理，用空间换时间，更加接近朴素算法，是一种暴力数据结构。

例题1

例如最经典的区间修改区间查询，若用树状数组来做就显得过于麻烦了。而用线段树做这道题，虽然通用，但马亮比较大，非常不友好。于是一种 \(O(nlogn)\) 的解法出现了——分块。

思路

将整个序列分为 $\sqrt{n} $ 块，每个块长自然为 \(\sqrt{n}\)，于是采用大段维护，小段朴素的思路。在查询或修改的范围 \([l,r]\) 包含完整的块时，直接通过 add 数组标记该区间整体的变化。而左右两端零散的块直接朴素枚举，肥肠暴力。

代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
const int N = 2e5+5;

int n,m,a[N],L[N],R[N],pos[N],sum[N],add[N];

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

int query(int l,int r)
{
    int p = pos[l],q = pos[r];
    ll ans = 0;
    if (p == q)
    {
        for (int i = l;i <= r;i++) ans += a[i] + add[p];
        return ans;
    }
    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] + add[p];
    for (int i = L[q];i <= r;i++) ans += a[i] + add[q];
    
    return ans;
}


signed main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int t = sqrt(n);
    
    for (int i = 1;i <= t;i++)
        L[i] = (i-1) * t + 1,R[i] = i * t;
    if (R[t] < n) t++,R[t] = n,L[t] = R[t-1] + 1;
    
    for (int i = 1;i <= t;i++)
        for (int j = L[i];j <= R[i];j++)
            pos[j] =  i,sum[i] += a[j];
    
    for (int i = 1;i <= m;i++)
    {
        char op[2];
        scanf("%s",op);
        int l,r,d;
        if (op[0] == 'Q')
        {
            cin >> l >> r;
            cout << query(l,r) << endl;
        }
        else 
        {
            cin >> l >> r >> d;
            modify(l,r,d);
        }
    }
    return 0;
}

例题2

蒲公英

本题在线求解区间众数，众数不满足区间可加性，因此若用线段树和树状数组做较难维护，所以考虑分块。

做法

鸽

• 预处理每个区间 \([l,r]\) 中每个数出现的个数。