【模板】线段树 1

        
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

        #include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;

typedef  long long ll;
ll n,m;
ll a[maxn];


// ---- block
struct Block {
    ll block;
    ll t;
    ll pos[maxn];
    ll st[maxn];
    ll ed[maxn];

    ll sum[maxn];
    ll addflag[maxn];

    void init(){
        block = sqrt(n);
        t = n / block;
        if( n % block) t++;
        for(ll i = 1;i <= t ;++i ) // i: 1->t
        {
            st[i] = (i-1) * block + 1;
            ed[i] = i * block;
        }
        ed[t] = n; // 修正最后一个快的结尾
        for(ll i = 1;i <= n ;++i ) // i: 1->n
        {
            pos[i] = (i-1) / block + 1;
        }

        for(ll i = 1;i <= t ;++i ) // i: 1->t
        {
            for(ll j = st[i];j <= ed[i] ;++j ) // j: 1->n
            {
                sum[i] += a[j];
            }
        }
    }

    //区间修改 
    void update(ll L,ll R,ll d) {
        ll p = pos[L],q = pos[R];
        if( p == q) {
            for(ll i = L;i <= R;i++) {
                a[i] +=d;
                sum[p] +=d; 
            }
        }
        else {
            for(ll i = p+1;i <= q-1;i++) 
                addflag[i] += d;
            for(ll i = L; i <= ed[p] ;i++) {
                a[i] += d;
                sum[p] += d;
            }
            for(ll i = st[q];i <= R;i++) {
                a[i] += d;
                sum[q] += d;
            }
        }
    }

    long long query(ll L,ll R) {
        long long ret = 0;
        ll p = pos[L], q = pos[R];
        if( p == q) {
            for(ll i = L;i <= R;i++) {
                ret += a[i];
                ret += addflag[p];
            }
        }
        else {
            for(ll i = p+1;i<=q-1;i++) {
                ret += sum[i];
                ret += addflag[i] * (ed[i]-st[i]+1);
            }
            for(ll i = L; i <= ed[p] ;i++) {
                ret += a[i];
                ret += addflag[p];
            }
            for(ll i = st[q];i <= R;i++) {
                ret += a[i];
                ret += addflag[q];
            }
        }
        return ret;
    }
} myblock;


//读取数据
void init() {
    std::cin >> n;
    std::cin >> m;
    for(ll i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
    }
    myblock.init();
}



int main () {
    init();
    for(ll i = 1;i <= m ;++i ) // i: 1->m
    {
        ll opt;
        std::cin >> opt;
        if(opt == 1) {
            ll x,y,k;
            std::cin >> x >> y >> k;
            myblock.update(x, y, k);
        }
        else {
            ll x,y;
            std::cin >> x >> y;
            cout << myblock.query(x, y) << "\n";
        }
    }
    
    return 0;
}