30pts 线段树求调（玄关）

#include<bits/stdc++.h>
using namespace std;

struct node
{
    long long l, r;
    long long sum, add;
} tree[400005];

long long n, m;
long long a[100005];

void up(long long p)
{
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
    return;
}

void build(long long p, long long l, long long r)
{
    tree[p].l = l, tree[p].r = r;
    if (l == r)
    {
        tree[p].sum = a[l];
        return;
    }
    long long mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
    return;
}

void spread(long long p)
{
    if (tree[p].add)
    {
        tree[p << 1].sum += tree[p].add * (tree[p << 1].r - tree[p << 1].l + 1);
        tree[p << 1 | 1].sum += tree[p].add * (tree[p << 1].r - tree[p << 1].l + 1);
        tree[p << 1].add += tree[p].add;
        tree[p << 1 | 1].add += tree[p].add;
        tree[p].add = 0;
    }
    return;
}

void change(long long p, long long l, long long r, long long k)
{
    if (l <= tree[p].l && r >= tree[p].r)
    {
        tree[p].sum += k * (tree[p].r - tree[p].l + 1);
        tree[p].add += k;
        return;
    }
    spread(p);
    long long mid = tree[p].l + tree[p].r >> 1;
    if (l <= mid)
        change(p << 1, l, r, k);
    if (r > mid)
        change(p << 1 | 1, l, r, k);
    up(p);
    return;
}

long long ask(long long p, long long l, long long r)
{
    if (l <= tree[p].l && r >= tree[p].r)
        return tree[p].sum;
    spread(p);
    long long mid = tree[p].l + tree[p].r >> 1;
    long long val = 0;
    if (l <= mid)
        val += ask(p << 1, l, r);
    if (r > mid)
        val += ask(p << 1 | 1, l, r);
    return val;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (long long i = 1; i <= n; ++i)
        cin >> a[i];
    build(1, 1, n);
    while (m--)
    {
        long long op, l, r, k;
        cin >> op >> l >> r;
        if (op & 1)
        {
            cin >> k;
            change(1, l, r, k);
        }
        else
            cout << ask(1, l, r) << '\n';
    }
    return 0;
}