引入

分块的基本思想是将一个长度为 n n n的段，分成 n \sqrt{n} n ​个块，每个块的长度为 n \sqrt{n} n ​

主要思想是大段维护、小段朴素；

说白了就是对于一个块来说，我们维护总体；而对于零散的点，我们直接暴力就行；

---

分块的时间复杂度一般是 O ( n n ) O(n\sqrt{n}) O(nn ​)，比线段树、树状数组的 O ( n l o g n ) O(nlogn) O(nlogn)是慢的；

但是线段树、树状数组再维护不满足区间可加、可减性的信息是比较麻烦的；

例题

一个简单的整数问题2

题面

传送门

思路

这题需要区间加、以及区间求和；

首先我们将这个长度为 n n n的整体划分成 n \sqrt{n} n ​个块；

题目给定我们 [ L , R ] [L,R] [L,R]我们需要分为两种情况；

一种是在某一个块内，另一种是横跨了多个块；

---

首先考虑在块内的情况，因为每个块的长度为 n \sqrt{n} n ​；

因此这种就属于零散的点，至多也就 n \sqrt{n} n ​个，因此我们直接暴力即可；

---

接着考虑横跨多个块的部分；

不难发现，我们至多会有 2 2 2个不完整的块；

而中间都是完整的块；

对于完整块来说，我们可以采取线段树懒标记的思想，就可以实现总体加、求和；

而对于不完整的，我们和之前一样，暴力就行；

---

注意

代码中的sum(i),add(i)表示第 i i i块的信息；

其中sum(i)是已经算上了add(i)的，而add(i)的用处在暴力处理零散点的时候出现；

---

有一点值得注意，在处理整块的时候

我们是直接给sum加上d*len

有些块的长度是不足len的，但是没有关系；

因为我们根本就不会访问到多加的部分；

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10,M = 350;

int n,m,len;

int a[N];
//sum(i) 表示第i个完整块的总和(算上add后)
//add(i) 表示第i个完整块应该加上多少
ll sum[M],add[M];

int get(int x){ //映射 位置 -> 第几块
    return x / len;
}

void modify(int l,int r,int d){
    //如果只在一个块内 直接暴力
    if(get(l) == get(r)){
        for(int i=l;i<=r;++i){
            sum[get(i)] += d;
            a[i] += d;
        }
    }
    //如果横跨多个块，大段维护，局部朴素
    else{
        //先处理朴素
        int i=l,j=r;
        while(get(i) == get(l)){
            a[i] += d;
            sum[get(i)] += d;
            ++i;
        }
        while(get(j) == get(r)){
            a[j] += d;
            sum[get(j)] += d;
            --j;
        }
        //再处理整块
        for(int block = get(i);block<=get(j);++block){
            //可能会多加 但是不影响 因为我们根本不会访问到多加的部分
            sum[block] += d * len;
            add[block] += d;
        }
    }
}

ll query(int l,int r){
    ll ret = 0;
    //同理 如果只有一块
    if(get(l) == get(r)){
        for(int i=l;i<=r;++i){
            ret += a[i] + add[get(i)];
        }
    }
    //如果横跨多块
    else{
        int i = l,j = r;
        while(get(i) == get(l)){
            ret += a[i] + add[get(i)];
            ++i;
        }
        while(get(j) == get(r)){
            ret += a[j] + add[get(j)];
            --j;
        }
        for(int block = get(i);block<=get(j);++block){
            ret += sum[block];  
        }
    }
    return ret;
}

void solve(){
    cin >> n >> m;
    len = sqrt(n);
    for(int i=1;i<=n;++i){
        cin >> a[i];
        sum[get(i)] += a[i];
    }
    char op[2];
    int l,r,d;
    while(m--){
        cin >> op >> l >> r;
        if(op[0] == 'C'){
            cin >> d;
            modify(l,r,d);
        }
        else{  
            cout << query(l,r) << '\n';
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}