线段树之：【懒标记的原理】【懒标记模板的分析】

引子

印象里面最原始线段树模板不是可以利用差分进行区间修改吗，

为什么还要引入懒标记版本的区间修改呢？

1.差分版的区间修改本质是不变的，仍然是单点修改，并不是真正的区间修改，

那个解决的问题有局限性。

2.这个版本的区间修改，是真正的区间修改，modify()都变了，还加了pushdown（）操作

一.懒标记的原理

二.懒标记模板的分析 

 三.题意

//解析版

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int n,m;
int w[N];
struct Node
{
    int l,r;
    LL sum,add;
}tr[N*4];


void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}



void pushdown(int u)
{
    //用三个变量分别把根节点，左儿子和右儿子表示出来
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    
    if(root.add)  //如果根节点上是有标记的，才这么做
    {
        left.add+=root.add, left.sum+=(LL)(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;
        root.add=0;  //清空根节点上的标记 
    }
}


void build(int u,int l,int r)
{
    tr[u]={l,r};
    if(l==r)
    {
        tr[u]={l,r,w[r],0};
        return;
    }
    
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}


void modify(int u,int l,int r,int d)  //区间修改模板
{
    if(tr[u].l>=l&&tr[u].r<=r) 
    {
        tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
    }
    else //第二种情况表示，当前区间太大,一定要分裂
    {
        /*
        往下分裂的话就一定要pushdown
        因为当前区间的标记，不能再表示统一的标志了，
        祖宗不能承担，要传递给子区间
        */
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)
        {
            modify(u<<1,l,r,d);
        }
        if(r>mid)
        {
            modify(u<<1|1,l,r,d);
        }
        
        pushup(u);
    }
}

LL query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        return tr[u].sum;
    }
    
    //现在由于要开始查询子区间了，所以先pushdown一下信息
    pushdown(u);
    
    int mid=tr[u].l+tr[u].r>>1;
    LL sum=0;
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
    
    return sum;
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    
    build(1,1,n);
    
    int l,r,d;
    char op[2];
    
    while(m--)
    {
        scanf("%s%d%d",op,&l,&r);
        if(*op=='C')
        {
            scanf("%d",&d);
            modify(1,l,r,d);
        }
        else 
        {
            printf("%lld\n",query(1,l,r));
        }
    }
    
    
    return 0;
}


           

//清爽版 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    LL sum, add;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else    // 一定要分裂
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d);
        if (r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}


int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    build(1, 1, n);

    char op[2];
    int l, r, d;

    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C')
        {
            scanf("%d", &d);
            modify(1, l, r, d);
        }
        else printf("%lld\n", query(1, l, r));
    }

    return 0;
}