经典区间求和、区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
struct segment_tree{
    int L, R, size;
    i64 lazy, ans;
} a[400010];
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    auto up = [&](int x) -> void
    {
        a[x].ans = a[x << 1].ans + a[(x << 1) + 1].ans;
    };
    auto down = [&](int x) -> void
    {
        if (!a[x].lazy)
            return;
        a[x].ans += a[x].lazy * a[x].size;
        if (a[x].L != a[x].R){
            a[x << 1].lazy += a[x].lazy;
            a[(x << 1) + 1].lazy += a[x].lazy;
        }
        a[x].lazy = 0;
    };
    auto build = [&](auto bulid, int x, int L, int R) -> void
    {
        a[x].L = L, a[x].R = R, a[x].size = R - L + 1;
        if (L == R){
            cin >> a[x].ans;
            return;
        }
        const int mid = L + R >> 1;
        bulid(bulid, x << 1, L, mid);
        bulid(bulid, (x << 1) + 1, mid + 1, R);
        up(x);
    };
    auto change = [&](auto change, int x, int L, int R, i64 val) -> void
    {
        down(x);
        if (a[x].L > R || a[x].R < L)
            return;
        if (a[x].L >= L && a[x].R <= R){
            a[x].lazy += val;
            down(x);
            return;
        }
        change(change, x << 1, L, R, val);
        change(change, (x << 1) + 1, L, R, val);
        up(x);
    };
    auto query = [&](auto query, int x, int L, int R) -> i64
    {
        down(x);
        if (a[x].L > R || a[x].R < L)
            return 0;
        if (a[x].L >= L && a[x].R <= R)
            return a[x].ans;
        return query(query, x << 1, L, R) + query(query, (x << 1) + 1, L, R);
    };
    build(build, 1, 1, n);
    while (m--){
        int opt, L, R;
        cin >> opt >> L >> R;
        if (opt == 1){
            i64 x;
            cin >> x;
            change(change, 1, L, R, x);
        }
        else
            cout << query(query, 1, L, R) << endl;
    }
    return 0;
}