题后感

~~码量也太大了吧~~

小记

题解网上有，但是有关这个lazytag我要提一嘴，我建议不要记它，你只需知道修改的区间没有整体破坏时，其内部的元素内容暂不做修改

code 码量真大

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll tree[400020]={0};
ll save[400020]={0};
ll a[100020]={0};
void keep(ll now,ll len,ll k)
{//代表传给后代值，现在区间，区间长度，传递值
    save[now]+=k;//给子节点的值，先在你这保留着，反正也没拆开
    tree[now]+=len*k;//区间值
}

void breakdown(ll now,ll l,ll r)//这个区间要被拆开来，所以保留的值传给后代
{//代表当前区间，区间左端点，区间右端点
    ll mid=(l+r)/2;
    keep(2*now,mid-l+1,save[now]);
    keep(2*now+1,r-mid,save[now]);
    save[now]=0;//传递过去了，自然要清空
}

void add(ll now,ll l,ll r,ll L,ll R,ll k)//
{
    if(l>=L&&r<=R)//如果当前区间被完全包裹
        keep(now,r-l+1,k);//不用分开来传递了
    else
    {
        if(!(r<L||l>R))//如果有交集
        {
            breakdown(now,l,r);//要被拆开了，把保留着的值传给子节点
            int mid=(l+r)/2;
            add(2*now,l,mid,L,R,k);
            add(2*now+1,mid+1,r,L,R,k);
            tree[now]=tree[2*now]+tree[2*now+1];
        }
    }
}

void build(ll now,ll l,ll r)
{
    if(l==r)
    {
        tree[now]=a[l];
        return;
    }
    ll mid=(l+r)/2;
    build(2*now,l,mid);
    build(2*now+1,mid+1,r);
    tree[now]=tree[2*now]+tree[2*now+1];
}

ll query(ll now,ll l,ll r,ll L,ll R)//用于找出完全组成待找区间的区间
{
    if(l>=L&&r<=R) return tree[now];
    else if(!(r<L||l>R))
    {
        ll mid=(l+r)/2;
        breakdown(now,l,r);
        return query(2*now,l,mid,L,R)+query(2*now+1,mid+1,r,L,R);
    }
    else return 0;
}
int main()
{
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);//构建线段树，
    while(m--)
    {
        ll op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            ll k;
            cin>>k;
            add(1,1,n,x,y,k);//待加区间肯定被包裹在根区间里，
        }
        else cout<<query(1,1,n,x,y)<<endl;
    }
    return 0;
}