[Luogu 3372] Line Segment Tree Template (lazy Marker)

lazy thought:
For example, when we want to add C to [a,b] interval, we find an interval which is included by [a,b] interval, then sum + = c* (edge [i], R - edge [i], L + 1) of this interval, and label this interval lazy. If normal practice should be to increase the interval of the interval c, but lazy marker is to return directly, not to update the sum of the interval, when the next need to use the value of the interval, then update again, thus avoiding a lot of useless operations.

Structural Definition:

```struct node{
ll lazy,pre;    //Lazy stands for lazy markers, pre stands for intervals and
int l,r;        //Interval boundary
}edge[maxn*4];
```

Tree Building Code:

```void build(int p,int l,int r)
{
edge[p].l=l,edge[p].r=r;
if(l == r){
edge[p].pre=a[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
edge[p].pre=edge[p<<1].pre+edge[p<<1|1].pre;
}
```

Update the interval code:
The lazy tag is mainly used here.

```void change(int p,int x,int y,ll z)
{
if(edge[p].l >= x && edge[p].r <= y){       //If the interval is overwritten, change its value
edge[p].lazy+=z;
edge[p].pre += z*(ll)(edge[p].r-edge[p].l+1);
return ;
}
spread(p);       //The interval is uncovered and the lazy marker is lowered. At this time, the subinterval of the interval is not updated.
int mid=(edge[p].l+edge[p].r)>>1;
if(x <= mid)
change(p<<1,x,y,z);     //If the interval to be modified covers the left son, update the left son
if(mid <y)      //Cover the right son, update the right son
change(p<<1|1,x,y,z);
edge[p].pre=edge[p<<1].pre+edge[p<<1|1].pre;   //Maintenance value = left son + right son
return ;
}
```

Here, when the interval is overwritten, it return s after the update, instead of continuing to update the sub-interval, which is the idea of lazy markup.
When will the value of the child node be updated again?
When the interval is not covered, the sub-interval is accessed. At this time, the lazy marker is lowered to the sub-interval, and the value of edge[i].pre and lazy are updated.

```void spread(int p)
{
if(edge[p].lazy){
edge[p<<1].lazy+=edge[p].lazy;
edge[p<<1|1].lazy+=edge[p].lazy;
edge[p<<1].pre+=edge[p].lazy*(ll)(edge[p<<1].r-edge[p<<1].l+1);
edge[p<<1|1].pre+=edge[p].lazy*(ll)(edge[p<<1|1].r-edge[p<<1|1].l+1);
edge[p].lazy=0;     //lazy is assigned a value of 0 after decentralization
}
}
```

Here is the code for finding the sum of intervals:

```void ask(int p,ll x,ll y)
{
if(edge[p].l >= x && edge[p].r <=y){     //If the interval is completely covered, add the interval sum directly.
ans+=edge[p].pre;
return ;
}
int mid = (edge[p].l+edge[p].r)>>1;
if(x <= mid)
if(mid < y)
}
```

Here is the AC code:

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define memset(a,b) memset(a,b,sizeof(a))
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
const int maxn=1e6+10;

ll a[maxn];
struct node{
ll lazy,pre;
int l,r;
}edge[maxn*4];
ll ans;

void build(int p,int l,int r)
{
edge[p].l=l,edge[p].r=r;
if(l == r){
edge[p].pre=a[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
edge[p].pre=edge[p<<1].pre+edge[p<<1|1].pre;
}
{
if(edge[p].lazy){
edge[p<<1].lazy+=edge[p].lazy;
edge[p<<1|1].lazy+=edge[p].lazy;
edge[p<<1].pre+=edge[p].lazy*(ll)(edge[p<<1].r-edge[p<<1].l+1);
edge[p<<1|1].pre+=edge[p].lazy*(ll)(edge[p<<1|1].r-edge[p<<1|1].l+1);
edge[p].lazy=0;
}
}
void change(int p,int x,int y,ll z)
{
if(edge[p].l >= x && edge[p].r <= y){
edge[p].lazy+=z;
edge[p].pre += z*(ll)(edge[p].r-edge[p].l+1);
return ;
}
int mid=(edge[p].l+edge[p].r)>>1;
if(x <= mid)
change(p<<1,x,y,z);
if(mid <y)
change(p<<1|1,x,y,z);
edge[p].pre=edge[p<<1].pre+edge[p<<1|1].pre;
return ;
}
{
if(edge[p].l >= x && edge[p].r <=y){
ans+=edge[p].pre;
return ;
}
int mid = (edge[p].l+edge[p].r)>>1;
if(x <= mid)
if(mid < y)
}
int main()
{
int n,m,op,x,y;
ll k;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n);

for(int i=1;i<=m;i++){
scanf("%d",&op);
ans=0;
if(op == 1){
scanf("%d %d %lld",&x,&y,&k);
change(1,x,y,k);
}
else{
scanf("%d %d",&x,&y);