思路: 线段树 (区间插入, 区间查询)

区间插入板子

还不会线段树的看这里: https://www.bilibili.com/video/BV1qY411n7Qs/?share_source=copy_web&vd_source=fcfe5417126b8b1ac8277353f33dc3e0

线段树节点:

struct Node {
    int L, R;
    ll lazy;    // 懒标记 
    ll val;     // 区间和 
} tr[N << 2];

懒标记的作用: 我们进行区间插入的时候, 比如说我们在 [1, 223] 这个区间插入 5, 那么在线段树中, 这个 [1, 223] 区间可能会被分解成 [1,128], [129, 192], [193, 208], [209, 216], [217, 220], [221, 222], [223, 223] 这样几个区间; 我们递归到 [1, 128] 这个节点时, 当前节点的区间被包含在插入区间 [1, 223] 中, 也就是当前区间的每一位我们都插入一个 5, 我们令当前区间的lazy += 5, 表示当前区间的每一位都插入一个 5, 这样就不需要再往下递归;

看 insert() 方法, 就是实现上述的逻辑:

// 插入 
void insert(int rt, int x, int y, int v) {
    if (l == x && r == y) {
        tr[rt].lazy += v;
        tr[rt].val += (r - l + 1L) * v;
        return;
    }

    down(rt);
    int m = mid;

    if (y <= m)
        insert(lson, x, y, v);
    else if (x > m)
        insert(rson, x, y, v);
    else 
        insert(lson, x, m, v), 
        insert(rson, m + 1, y, v);

    up(rt);
}

可以发现, 除了上述逻辑, 每到一个节点, 我们都会做一个 down() 的动作:

// push_down(), 父节点懒标记下传 
void down(int rt) {
    // 当前区间有懒标记 
    if (tr[rt].lazy != 0) {
        ll lz = tr[rt].lazy;
        // 下传给左孩子 
        tr[lson].lazy += lz;
        tr[lson].val += (tr[lson].R - tr[lson].L + 1) * lz; 
        // 下传给右孩子 
        tr[rson].lazy += lz;
        tr[rson].val += (tr[rson].R - tr[rson].L + 1) * lz; 
        // 下传完清空当前节点的懒标记 
        tr[rt].lazy = 0;
    }
}

它的作用是把父节点懒标记下传, 通过这样 懒住 和 下传 的操作, 我们才能实现 区间插入 的操作的时间复杂度趋近于 log 级别

完整代码实现:

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define lson rt<<1                  // 左孩子下标 
#define rson rt<<1|1                // 右孩子下标 
#define mid (tr[rt].L+tr[rt].R)>>1  // 区间 [L, R] 的中点 
#define l tr[rt].L                  // 节点区间 [L, R] --> [l, r] , coding 比较方便 
#define r tr[rt].R

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
int _, n, m;

struct Node {
    int L, R;
    ll lazy;    // 懒标记 
    ll val;     // 区间和 
} tr[N << 2];

// 建树 
void build(int rt, int L, int R) {
    tr[rt] = {L, R};
    if (l == r)
        return ;
    int m = mid;
    build(lson, l, m);
    build(rson, m + 1, r);
}

// push_up() 方法, 孩子向父节点传递数据 
void up(int rt) {
    tr[rt].val = tr[lson].val + tr[rson].val;
}

// push_down(), 父节点懒标记下传 
void down(int rt) {
    // 当前区间有懒标记 
    if (tr[rt].lazy != 0) {
        ll lz = tr[rt].lazy;
        // 下传给左孩子 
        tr[lson].lazy += lz;
        tr[lson].val += (tr[lson].R - tr[lson].L + 1) * lz; 
        // 下传给右孩子 
        tr[rson].lazy += lz;
        tr[rson].val += (tr[rson].R - tr[rson].L + 1) * lz; 
        // 下传完清空当前节点的懒标记 
        tr[rt].lazy = 0;
    }
}

// 插入 
void insert(int rt, int x, int y, int v) {
    if (l == x && r == y) {
        tr[rt].lazy += v;
        tr[rt].val += (r - l + 1L) * v;
        return;
    }

    down(rt);
    int m = mid;

    if (y <= m)
        insert(lson, x, y, v);
    else if (x > m)
        insert(rson, x, y, v);
    else 
        insert(lson, x, m, v), 
        insert(rson, m + 1, y, v);

    up(rt);
}

// 查询方法 
ll calc(int rt, int x, int y) {
    if (x == l && y == r)
        return tr[rt].val;
    down(rt);
    int m = mid;
    if (y <= m)
        return calc(lson, x, y);
    else if (x > m)
        return calc(rson, x, y);
    else 
        return calc(lson, x, m) + calc(rson, m + 1, y);
}

void solve() {
    cin >> n >> m;
    build(1, 1, n);
    ll t;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        insert(1, i, i, t);
    }

    while (m--) {
        string op;
        ll x, y, t;
        cin >> op;

        if ("C" == op) {
            cin >> x >> y >> t;
            insert(1, x, y, t);
        } else {
            cin >> x >> y;
            cout << calc(1, x, y) << endl;
        }
    }
}

int main() {
//  IOS
//  cin >> _;
//  for (int i = 1; i <= _; i++)
    solve();
    return 0;
}