分块模型

分块是一种暴力做法的优化。

基本思想是把要操作的对象分为根号n份，然后按份进行操作。

模板题:

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

struct Node {
    int l, r;
    LL sum, lazy;
} blk[N];

int n, m;
int len;
LL a[N];
int loc[N], idx;

void modify(int l, int r, LL val) {
    int idl = loc[l], idr = loc[r];
    if(idl == idr) {
        for(int i = l; i <= r; i ++ ) a[i] += val;
        blk[idl].sum += val * (r - l + 1);
    } else {
        for(int i = l; i <= blk[idl].r; i ++ ) a[i] += val;
        blk[idl].sum += val * (blk[idl].r - l + 1);
        for(int i = blk[idr].l; i <= r; i ++ ) a[i] += val;
        blk[idr].sum += val * (r - blk[idr].l + 1);
        for(int i = idl + 1; i < idr; i ++ ) {
            blk[i].lazy += val;
            blk[i].sum += val * (blk[i].r - blk[i].l + 1);
        }
    }
}

LL query(int l, int r) {
    int idl = loc[l], idr = loc[r];
    LL res = 0;
    if(idl == idr) {
        for(int i = l; i <= r; i ++ ) res += a[i] + blk[idl].lazy;
    } else {
        for(int i = l; i <= blk[idl].r; i ++ ) res += a[i] + blk[idl].lazy;
        for(int i = blk[idr].l; i <= r; i ++ ) res += a[i] + blk[idr].lazy;
        for(int i = idl + 1; i < idr; i ++ ) res += blk[i].sum;
    }
    return res;
}

int main() {
    cin.tie(0);
    cin >> n >> m;
    len = sqrt(n);
    
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        loc[i] = (i - 1) / len + 1;
        blk[loc[i]].sum += a[i];
        if((i - 1) % len == 0) blk[ ++ idx].l = i;
        if(i % len == 0) blk[idx].r = i;
    }
    
    char op[2];
    int xx, yy;
    LL ff;
    while(m -- ) {
        cin >> op;
        cin >> xx >> yy;
        if(xx > yy) swap(xx, yy);
        if(op[0] == 'C') {
            cin >> ff;
            modify(xx, yy, ff);
        } else {
            cout << query(xx, yy) << endl;
        }
    }
    
    return 0;
}