题目引出：

给出点集数以及命令数；
先将每一个点赋初值
Q a b 表示求出点集中从a到b的和
C a b c 表示将a到b的点全部加c

嗯，这又是一篇复习文章

首先我们把线段树用标记下传求的区间和代码上一下

#include<cstdio>
template <class T>
inline void read(T &x)
{
    x=0;int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
        if(ch<'0'||ch>'9')f=1;
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x*=f;
}
template <class T>
inline void write(T x)
{
    if(x<0)putchar('-'),x*=-1;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
struct tree
{
    long long int sum,add;
    inline void Add(long long int l,long long int r,long long int v)
    {
        add+=v;
        sum+=(r-l+1)*v;
    }
}bt[5000000];
void build(long long int k,long long int l,long long int r)
{
    if(l==r)return read(bt[k].sum);
    long long int mid=l+r>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    bt[k].sum=bt[k<<1].sum+bt[k<<1|1].sum;
}
void pushdown(long long int k,long long int l,long long int r,long long int mid)
{
    bt[k<<1].Add(l,mid,bt[k].add);
    bt[k<<1|1].Add(mid+1,r,bt[k].add);
    bt[k].add=0;
}
void modify(long long int k,long long int l,long long int r,long long int x,long long int y,long long int v)
{
    if(l>=x&&r<=y)return bt[k].Add(l,r,v);
    pushdown(k,l,r,l+r>>1);
    long long int mid=l+r>>1;
    if(x<=mid)modify(k<<1,l,mid,x,y,v);
    if(y>mid)modify(k<<1|1,mid+1,r,x,y,v);
    bt[k].sum=bt[k<<1].sum+bt[k<<1|1].sum;
}
long long int query(long long int k,long long int l,long long int r,long long int x,long long int y)
{
    if(l>=x&&r<=y)return bt[k].sum;
    long long int res=0;
    long long int mid=l+r>>1;
    pushdown(k,l,r,l+r>>1);
    if(x<=mid)res+=query(k<<1,l,mid,x,y);
    if(y>mid)res+=query(k<<1|1,mid+1,r,x,y);
    return res;
}
long long int n,q,a,b,c;
char s;
int main()
{
    read(n);read(q);
    build(1,1,n);
    while(q--)
    {
        scanf(" %c",&s);
        read(a);read(b);
        if(s=='Q')
        {
            write(query(1,1,n,a,b));
            putchar(10);
        }
        if(s=='C')
        {
            read(c);
            modify(1,1,n,a,b,c);
        }
    }
    return 0;
}

不得不说：这代码真长……

and then，让我们来说一下标记永久化 标记永久化就是不需要标记下传，每次求区间和的时候只需要计算子节点对当前节点的影响

所以

我们第一步就是修改函数 我们把标记函数修改成

void modify(long long int k,long long int l,long long int r,long long int x,long long int y,long long int v)
{
    if(l>=x&&r<=y)return bt[k].Add(l,r,v);
    if(y<l||x>r)return;
    long long int mid=l+r>>1;
    bt[k].sum+=(min(r,y)-max(l,x)+1)*v;
    if(x<=mid)modify(k<<1,l,mid,x,y,v);
    if(y>mid)modify(k<<1|1,mid+1,r,x,y,v);
}

我们可以看见，标记下传是标记完然后最后算父节点

但是标记永久化是直接父节点加上这次标记涉及到的他的子孙的个数。 也就是说

bt[k].sum+=(min(r,y)-max(l,x)+1)*v;

这一句很重要 当前区间和标记区间是两个不同的区间 我们把他看成一个数轴

我们用最小函数求最左边的右节点，用最大函数求最右边的左节点，再求这之中的个数，最后乘v 这就是标记永久化对父节点的修改

第二步就是修改查询

long long int query(long long int k,long long int l,long long int r,long long int x,long long int y)
{
    if(l>=x&&r<=y)return bt[k].sum+bt[k].add*(r-l+1);
    if(y<l||x>r)return 0;
    long long int res=bt[k].add*(min(r,y)-max(l,x)+1);
    long long int mid=l+r>>1;
    if(x<=mid)res+=query(k<<1,l,mid,x,y);
    if(y>mid)res+=query(k<<1|1,mid+1,r,x,y);
    return res;
}

emmmm，跟修改差不多 就是如果完全包含的话返回要加上这个节点的标记

好了，这里还有很重要的一步

我当年就WA在这里……

就是Add函数一定要修改……（记住啊）

inline void Add(long long int l,long long int r,long long int v)
{
        add+=v;//sum+=(r-l+1)*v;
}

看我注释掉的那个 在修改函数里他已经

bt[k].sum+=(min(r,y)-max(l,x)+1)*v;

修改了父节点，所以在加标记的时候并不需要修改父节点

好了，天下太平，现在奉上代码

#include<cstdio>
using namespace std;
long long int max(long long int  a,long long int  b)
{
    return a>b? a:b;
}
long long int min(long long int  a,long long int  b)
{
    return a>b? b:a;
}
template <class t>
inline void read(t &x)
{
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
        if(ch<'0'||ch>'9')f=1;
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x*=f;
}
template <class T>
inline void write(T x)
{
    if(x<0)putchar('-'),x*=-1;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
struct tree
{
    long long int sum,add;
    inline void Add(long long int l,long long int r,long long int v)
    {
        add+=v;//sum+=(r-l+1)*v;
    }
}bt[5000000];
void build(long long int k,long long int l,long long int r)
{
    if(l==r)return read(bt[k].sum);
    long long int mid=l+r>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    bt[k].sum=bt[k<<1].sum+bt[k<<1|1].sum;
}
void modify(long long int k,long long int l,long long int r,long long int x,long long int y,long long int v)
{
    if(l>=x&&r<=y)return bt[k].Add(l,r,v);
    if(y<l||x>r)return;
    long long int mid=l+r>>1;
    bt[k].sum+=(min(r,y)-max(l,x)+1)*v;
    if(x<=mid)modify(k<<1,l,mid,x,y,v);
    if(y>mid)modify(k<<1|1,mid+1,r,x,y,v);
}
long long int query(long long int k,long long int l,long long int r,long long int x,long long int y)
{
    if(l>=x&&r<=y)return bt[k].sum+bt[k].add*(r-l+1);
    if(y<l||x>r)return 0;
    long long int res=bt[k].add*(min(r,y)-max(l,x)+1);
    long long int mid=l+r>>1;
    if(x<=mid)res+=query(k<<1,l,mid,x,y);
    if(y>mid)res+=query(k<<1|1,mid+1,r,x,y);
    return res;
}
long long int n,q,a,b,c;
char s;
int main()
{
    read(n);read(q);
    build(1,1,n);
    while(q--)
    {
        scanf(" %c",&s);
        read(a);read(b);
        if(s=='Q')
        {
            write(query(1,1,n,a,b));
            putchar(10);
        }
        if(s=='C')
        {
            read(c);
            modify(1,1,n,a,b,c);
        }
    }
    return 0;
}