动态开点爆零悬关求调

// QQ答疑群：857242697
#include <iostream>
#define int long long
using namespace std;
const int N = 100005;
int val[2*N], tag[2*N];
int ls[2*N], rs[2*N];
int tot = 1, n, m;
void down(int x, int l, int r)
{
    if(tag[x])
    {
        if(!ls[x]) ls[x] = ++tot;
        if(!rs[x]) rs[x] = ++tot;
        tag[ls[x]] += tag[x];
        tag[rs[x]] += tag[x];
        int mid = (l+r)/2;
        val[ls[x]] += (mid-l+1)*tag[x];
        val[rs[x]] += (r-mid)*tag[x];
        tag[x] = 0;
    }
}
void bt(int &p, int l, int r, int x, int y)
{
    if(!p) p = ++tot;
    if(l == r) val[p] = y;
    else
    {
        int mid = (l+r)/2;
        if(x <= mid) bt(ls[p], l, mid, x, y);
        else bt(rs[p], mid+1, r, x, y);
        val[p] = val[ls[p]]+val[rs[p]];
    }
}
void upd(int &p, int l, int r, int L, int R, int x)
{
    if(!p) p = ++tot;
    if(L <= l && R >= r)
    {
        tag[p] += x;
        val[p] += (r-l+1)*x;
    }
    else
    {
        down(p, l, r);
        int mid = (l+r)/2;
        if(L <= mid) upd(ls[p], l, mid, L, R, x);
        if(R > mid) upd(rs[p], mid+1, r, L, R, x);
        val[p] = val[ls[p]]+val[rs[p]];
    }
}
int sum(int p, int l, int r, int L, int R)
{
    if(!p) return 0;
    if(L <= l && R >= r) return val[p];
    int mid = (l+r)/2, ans = 0;
    if(L <= mid) ans += sum(ls[p], l, mid, L, R);
    if(R >= mid+1) ans += sum(rs[p], mid+1, r, L, R);
    return ans;
}
signed main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        int x, t=1;
        cin >> x;
        bt(t, 1, n, i, x);
    }
    for(int i=1;i<=m;i++)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int l, r, x;
            cin >> l >> r >> x;
            int t = 1;
            upd(t, 1, n, l, r, x);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << sum(1, 1, n, l, r) << endl;
        }
    }
}

#include <iostream>
#define int long long
using namespace std;
const int N = 100005;
int val[2*N], tag[2*N];
int ls[2*N], rs[2*N];
int tot = 1, n, m;
void down(int x, int l, int r)
{
    if(tag[x])
    {
        if(!ls[x]) ls[x] = ++tot;
        if(!rs[x]) rs[x] = ++tot;
        tag[ls[x]] += tag[x];
        tag[rs[x]] += tag[x];
        int mid = (l+r)/2;
        val[ls[x]] += (mid-l+1)*tag[x];
        val[rs[x]] += (r-mid)*tag[x];
        tag[x] = 0;
    }
}
void bt(int &p, int l, int r, int x, int y)
{
    if(!p) p = ++tot;
    if(l == r) val[p] = y;
    else
    {
        int mid = (l+r)/2;
        if(x <= mid) bt(ls[p], l, mid, x, y);
        else bt(rs[p], mid+1, r, x, y);
        val[p] = val[ls[p]]+val[rs[p]];
    }
}
void upd(int &p, int l, int r, int L, int R, int x)
{
    if(!p) p = ++tot;
    if(L <= l && R >= r)
    {
        tag[p] += x;
        val[p] += (r-l+1)*x;
    }
    else
    {
        down(p, l, r);
        int mid = (l+r)/2;
        if(L <= mid) upd(ls[p], l, mid, L, R, x);
        if(R > mid) upd(rs[p], mid+1, r, L, R, x);
        val[p] = val[ls[p]]+val[rs[p]];
    }
}
int sum(int p, int l, int r, int L, int R)
{
    if(!p) return 0;
    if(L <= l && R >= r) return val[p];
    int mid = (l+r)/2, ans = 0;
    if(L <= mid) ans += sum(ls[p], l, mid, L, R);
    if(R >= mid+1) ans += sum(rs[p], mid+1, r, L, R);
    return ans;
}
signed main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        int x, t=1;
        cin >> x;
        bt(t, 1, n, i, x);
    }
    for(int i=1;i<=m;i++)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int l, r, x;
            cin >> l >> r >> x;
            int t = 1;
            upd(t, 1, n, l, r, x);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << sum(1, 1, n, l, r) << endl;
        }
    }
}