P3372 【模板】线段树 1

#include <iostream>
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %lld: ", x)
#define pn1(x) printf("Case %lld:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

typedef unsigned long long ull;

const LL N = 1e5 + 86;
LL n, m, a[N], d[N << 2], tag[N << 2];

void build(LL l, LL r, LL p)
{
    if (l == r)
    {
        d[p] = a[l];
        return;
    }
    LL m = l + ((r - l) >> 1);
    build(l, m, p << 1);
    build(m + 1, r, (p << 1) | 1);
    d[p] = d[p << 1] + d[(p << 1) | 1];
}

void update(LL l, LL r, LL c, LL nl, LL nr, LL p)
{
    if (l <= nl && r >= nr)
    {
        d[p] += (nr - nl + 1) * c;
        tag[p] += c;
        return;
    }
    LL m = nl + ((nr - nl) >> 1);
    if (tag[p])
    {
        tag[p << 1] += tag[p];
        tag[(p << 1) | 1] += tag[p];
        d[p << 1] += (m - nl + 1) * tag[p];
        d[(p << 1) | 1] += (nr - m) * tag[p];
        tag[p] = 0;
    }
    if (l <= m)
        update(l, r, c, nl, m, p << 1);
    if (r > m)
        update(l, r, c, m + 1, nr, (p << 1) | 1);
    d[p] = d[p << 1] + d[(p << 1) | 1];
    return;
}

LL getsum(LL l, LL r, LL nl, LL nr, LL p)
{
    if (l <= nl && nr <= r)
        return d[p];
    LL m = nl + ((nr - nl) >> 1);
    LL res = 0;
    //pn1(m);
    if (tag[p])
    {
        tag[p << 1] += tag[p];
        tag[(p << 1) | 1] += tag[p];
        d[p << 1] += (m - nl + 1) * tag[p];
        d[(p << 1) | 1] += (nr - m) * tag[p];
        tag[p] = 0;
    }
    if (l <= m)
        res += getsum(l, r, nl, m, p << 1);
    //pn1(m);
    if (r > m)
        res += getsum(l, r, m + 1, nr, (p << 1) | 1);
    return res;
}

int main()
{
    // IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    f(i, 1, n) cin >> a[i];
    build(1, n, 1);
    f(i, 1, m)
    {
        int temp, x, y, k;
        cin >> temp;
        if (temp & 1)
        {
            cin >> x >> y >> k;
            update(x, y, k, 1, n, 1);
        }
        else
        {
            cin >> x >> y;
            cout << getsum(x, y, 1, n, 1) << '\n';
        }
    }
    return 0;
}