P3372 【模板】线段树 1

题目描述
如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式
输入格式：
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：
输出包含若干行整数，即为所有操作2的结果。

思路：
题如其名 板子题 就是一个解决此类问题的模板 线段树的重点是push_down与update操作 我们来详细说一下这道题中的这两个操作。

首先是push_down

void push_down(int q,int l,int r)
{
    if(add[q])
    {
        int m=mid;
        segt[lson]+=(m-l+1)*add[q];
        segt[rson]+=(r-m)*add[q];
        add[lson]+=add[q];
        add[rson]+=add[q];
        add[q]=0;
    }   
}

因为我们都知道以为lazy tag的存在线段树才能变的高效 push_down的操作就是为了防止更新或查询操作的区间与一个有标记的区间交叉 当遇到这种情况的时候 我们就去下推标记 使得此次查询或更新操作的区间由若干个lazy tag的区间组成 没有交叉 从而达到logn的时间复杂度

update操作

void update(int q,int l,int r,int a,int b,int k)
{
    if(l>=a && r<=b)//包含了叶子节点的情况
    {
        segt[q]+=(r-l+1)*k;
        add[q]+=k;
        return;
    }
    int m=mid;
    push_down(q,l,r);
    if(a<=m) update(lson,l,m,a,b,k);
    if(b>m) update(rson,m+1,r,a,b,k);
    push_up(q);
}

update操作是为了去把每一步操作更新进当前区间 究其本质也是一个下推标记的过程 当我们得到一个操作区间的时候(a,b), 开始对初始区间进行二分压缩(l,r),当(l,r)在(a,b)之内的时候 在这里做上标记 知道我们需要的操作区间内全部做上标记 更新过程结束

AC代码：

#include<iostream>
using namespace std;
#define lson (q<<1)
#define rson (q<<1|1)
#define mid ((l+r)>>1)
#define ll long long
const int maxn=100005;
ll segt[maxn<<2];
ll add[maxn<<2];
int book[maxn<<2];
void push_up(int q)
{
    segt[q]=segt[lson]+segt[rson];
}

void build_tree(int q,int l,int r)
{
    add[q]=0;
    if(l==r)
    {
        segt[q]=book[l];
        return;
    }
    int m=mid;
    build_tree(lson,l,m);
    build_tree(rson,m+1,r);
    push_up(q);
}

void push_down(int q,int l,int r)
{
    if(add[q])
    {
        int m=mid;
        segt[lson]+=(m-l+1)*add[q];
        segt[rson]+=(r-m)*add[q];
        add[lson]+=add[q];
        add[rson]+=add[q];
        add[q]=0;
    }   
}

void update(int q,int l,int r,int a,int b,int k)
{
    if(l>=a && r<=b)
    {
        segt[q]+=(r-l+1)*k;
        add[q]+=k;
        return;
    }
    int m=mid;
    push_down(q,l,r);
    if(a<=m) update(lson,l,m,a,b,k);
    if(b>m) update(rson,m+1,r,a,b,k);
    push_up(q);
}

ll query(int q,int l,int r,int a,int b)
{
    if(r<a || l>b) return 0;
    if(l>=a && r<=b)
    {
        return segt[q];
    }
    int m=mid;
    push_down(q,l,r);
    return query(lson,l,m,a,b)+query(rson,m+1,r,a,b);  //也可以写成下面的形式
    //ll ans=0;
    //if(l<=m) ans+=query(lson,l,m,a,b);
    //if(r>m)  ans+=query(rson,m+1,r,a,b);
    //return ans;
}

int x,y,m,n;
long long k;
int main()
{
    cin >> m >> n;
    for(int i=1;i<=m;i++)
        cin >> book[i];
    build_tree(1,1,m);
    while(n--)
    {
        int tmp;
        cin>>tmp;
        if(tmp==1)
        {
            cin >> x >> y >> k;
            update(1,1,m,x,y,k);
        }else
        {
            cin >> x >> y;
            cout << query(1,1,m,x,y) << endl;
        }
    }
    return 0;
}