算法简介：舍径求真

分块思想，是一种把数据分为若干个块，以比正解略劣的复杂度通过题目的思想。适用于一些树形结构可以处理的区间类问题，比如说线段树之类的，分块可以做到基本平替。分块思想主要分为两个部分，完整块和边角块。对于查询的区间，肯定会有边角的至多两个块是不完整的，而不完整的块我们可以尝试暴力，完整的块我们也可以一块一块的数。这样几乎完全暴力的做法，就是分块的优势。

算法试用：忘形炼智

算法推导：漫行灵圃

那么继续上面的简介内容，我们不难想到，想要让边角小块的暴力与内部整块的枚举达到某种平衡，最为方便的，就是把每个块的大小设为 $\sqrt n$ 。这样就可以保证块的大小以及块的数量都是 $\sqrt n$ ，总体的复杂度自然也是 $O(n\sqrt n)$ 。

那么口说无凭，我们就以动态区间和这道线段树或者树状数组的模板题举例。

首先给出一个序列 $a$ 表示被操作的数组。数组长度为 11 。

$a = \big[1,2,-3,4,8,9,-2,3,0,-1,5\big]$

那么按照上面说的取根号作为块的大小，我们会得到下面的分块情况。每一个下标对应块的起始位置和终止位置一般是 $\left[\left\lfloor\cfrac{i}{B}\right\rfloor\times B\ ,\ \left(\left\lfloor\cfrac{i}{B}\right\rfloor+1\right)\times B\right)$ 。

$[1,2,-3],[4,8,9],[-2,3,0],[-1,5]$

那么首先考虑如何修改。对于修改操作，我们想想如何保证答案正确。首先对于整块我们定义 $res[x]$ 表示第 $x$ 个块的总和，这个非常好处理。但是，一些块也有可能会在讯问中被分开来，就会导致虽然整块答案正确，但是单独拎出来就不对了，那么为了保证正确性，我们还要记录一个 $base[x]$ 表示这个块总计的修改值。那么相对的，小块的处理涉及不到整块，直接在基础值$a[i]$ 上面修改即可。

那么询问如何应对？也简单，整块自然只需要用 $res[x]$ 累计。而小块，只需要初始值 $a[i]$ 在加上修改值 $base[i/B]$ 就可以了。

这就是用分块思想解决这道线段树模板题的方法。总体复杂度是 $O(n\sqrt n)$ ，接下来我们看代码。

算法演示：神机明悟

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

typedef long long ll;
const int N = 1e5 + 10;

int n, Q;
ll a[N];

int B;
ll ans[N], base[N];

inline void Input() {
    scanf("%d%d", &n, &Q);
    B = sqrt(n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        ans[i/B] += a[i];
    }
}

inline ll Query(int l, int r) {
    int idl = l / B, idr = r / B;
    ll res = 0;
    if(idl == idr) {
        for(int i = l; i <= r; i++) {
            res += a[i] + base[i/B];
        }
        return res;
    }
    for(int i = l; i < (idl + 1) * B; i++) {
        res += a[i] + base[i/B];
    }
    for(int i = idl + 1; i < idr; i++) {
        res += ans[i];
    }
    for(int i = idr * B; i <= r; i++) {
        res += a[i] + base[i/B];
    }
    return res;
}

inline void Modify(int l, int r, int x) {
    int idl = l / B, idr = r / B;
    if(idl == idr) {
        for(int i = l; i <= r; i++) {
            a[i] += x; ans[i/B] += x;
        }
        return ;
    }
    for(int i = l; i < (idl + 1) * B; i++) {
        a[i] += x; ans[i/B] += x;
    }
    for(int i = idl + 1; i < idr; i++) {
        ans[i] += 1LL * B * x;
        base[i] += x;
    }
    for(int i = idr * B; i <= r; i++) {
        a[i] += x; ans[i/B] += x;
    }
}

inline void Work() {
    char op; int l, r, x;
    while(Q--) {
        scanf(" %c", &op);
        if(op == 'Q') {
            scanf("%d%d", &l, &r);
            printf("%lld\n", Query(l, r));
        }
        else {
            scanf("%d%d%d", &l, &r, &x);
            Modify(l, r, x);
            // for(int i = 1; i <= n; i++) {
            //     cout << a[i] + base[i/B] << ' ';
            // }
            // cout << endl;
        }
    }
}

int main() {
    Input();
    Work();
    return 0;
}