线段树动态开点

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define endl '\n'
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 10;
ll n, m, root = 0, cnt = 0, ls[MAXN << 2], rs[MAXN << 2], tag[MAXN << 2], sum[MAXN << 2];

void pushup(ll& root)
{
    sum[root] = sum[ls[root]] + sum[rs[root]];
    return;
}

void update_single(ll& root, ll l, ll r, ll x, ll val)
{
    if (!root)
        root = ++cnt;
    if (l == r)
    {
        sum[root] = val; 
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        update_single(ls[root], l, mid, x, val);
    else
        update_single(rs[root], mid + 1, r, x, val);
    pushup(root);
}

void pushdown(ll& root, ll l, ll r)
{
    ll mid = l + r >> 1;
    if (tag[root])
    {
        if (!ls[root])
            ls[root] = ++cnt;
        if (!rs[root])
            rs[root] = ++cnt;
        tag[ls[root]] += tag[root], tag[rs[root]] += tag[root];
        sum[ls[root]] += (mid - l + 1) * tag[root];
        sum[rs[root]] += (r - mid) * tag[root];
        tag[root] = 0;
    }
    return;
}

void update_interval(ll& root, ll l, ll r, ll x, ll y, ll val)
{
    if (r < x || l > y)
        return;
    if (!root)
        root = ++cnt;
    if (x <= l && r <= y)
    {
        sum[root] += val * (r - l + 1);
        tag[root] += val;
        return;
    }
    int mid = l + r >> 1;
    pushdown(root, l, r);
    if (x <= mid)
        update_interval(ls[root], l, mid, x, y, val);
    if (y >= mid + 1)
        update_interval(rs[root], mid + 1, r, x, y, val);
    pushup(root);
}

ll query(ll& root, ll l, ll r, ll x, ll y)
{
    if (r < x || l > y)
        return 0;
    if (!root)
        root = ++cnt;
    if (x <= l && r <= y)
        return sum[root];
    int mid = l + r >> 1;
    pushdown(root, l, r);
    ll ans = 0;
    if (x <= mid)
        ans += query(ls[root], l, mid, x, y);
    if (y >= mid + 1)
        ans += query(rs[root], mid + 1, r, x, y);
    return ans;
}

int main()
{
    IOS; cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, x; i <= n; ++i)
        cin >> x, update_single(root, 1, n, i, x);
    ll op, x, y, k;
    while (m--)
    {
        cin >> op;
        if (op == 1)
            cin >> x >> y >> k, update_interval(root, 1, n, x, y, k);
        else
            cin >> x >> y, cout << query(root, 1, n, x, y) << endl;
    }

    return 0;
}