洛谷 P3372

#include<bits/stdc++.h>

using namespace std;

// 线段树我默认每个数组下标都是从1开始的

void build(const vector<long long>& nums,vector<long long>& d,int s,int t,int p);
long long getSum(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p);
void update_plus(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p,long long c);

int main()
{
    int n,m,type,l,r;
    long long k;
    cin >> n >> m;
    vector<long long> nums(n+1), d(4*n+1), b(4*n+1, 0);  // 修改这里
    for(int i=1;i<=n;i++) cin>>nums[i];
    build(nums,d,1,n,1);
    while(m--)
    {
        cin >> type;
        if(type==2)
        {
            cin >> l >> r;
            cout << getSum(d,b,l,r,1,n,1) << '\n';
        }
        else if(type==1)
        {
            cin >> l >> r >> k;
            update_plus(d,b,l,r,1,n,1,k);
        }
    }
    return 0;
}


void build(const vector<long long>& nums,vector<long long>& d,int s,int t,int p)
{
    if(s==t)
    {
        d[p] = nums[s];
        return;
    }
    int m = s + ((t-s)>>1);
    build(nums,d,s,m,2*p);
    build(nums,d,m+1,t,2*p+1);
    d[p] = d[2*p] + d[2*p+1];
}

long long getSum(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p)
{
    if(l<=s && t<=r)
    {
        return d[p];
    }
    int m = s + ((t-s)>>1);
    long long sum=0;
    if (b[p] && s != t) //下传懒标记
    {  
        d[p*2] += b[p]*(m-s+1);
        d[p*2+1] += b[p]*(t-m);
        b[p*2] += b[p];
        b[p*2+1] += b[p];
        b[p] = 0;
    }
    if(l<=m) sum += getSum(d,b,l,r,s,m,2*p);
    if(r>m) sum += getSum(d,b,l,r,m+1,t,2*p+1);  //等价于r>=m+1
    return sum;
}

void update_plus(vector<long long>& d,vector<long long>& b,int l,int r,int s,int t,int p,long long c)
{
    // 当前区间为修改区间的子集时直接修改当前节点的值,修改后标记
    if (l <= s && t <= r) {
        d[p] += (t - s + 1) * c, b[p] += c;
        return;
    }
    int m = s + ((t - s) >> 1);
    if (b[p] && s != t) //下放标记(不会有s==t的情况因为s==t的时候肯定是lr的子区间已经直接return了)
    {
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p];
        b[p] = 0;
    }
    if (l <= m) update_plus(d, b, l, r, s, m, p * 2, c);
    if (r > m) update_plus(d, b, l, r, m + 1, t, p * 2 + 1, c);
    d[p] = d[p * 2] + d[p * 2 + 1];
}