P3372 【模板】线段树 1---洛谷

r囧r小猫 2023-07-17 11:28 20阅读 0赞

## 题目描述 ##

题目描述  
如题，已知一个数列，你需要进行下面两种操作：  
1.将某区间每一个数加上 k。  
2.求出某区间每一个数的和。  
输入格式  
第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

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

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：  
1.1 x y k：将区间 \[x, y\]内每个数加上 k。  
2.2 x y：输出区间 \[x, y\]内每个数的和。  
输出格式  
输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例  
输入 \#1 复制  
5 5  
1 5 4 2 3  
2 2 4  
1 2 3 2  
2 3 4  
1 1 5 1  
2 1 4  
输出 \#1 复制  
11  
8  
20  
说明/提示  
对于 30% 的数据：n≤8，m≤10。  
对于 70%的数据：n <=10^3,m≤10 ^4  
对于 100% 的数据:1≤n,m≤10 ^5。

保证任意时刻数列中任意元素的和在 \[-2^ 63, 2^63) 内。  
【样例解释】  
![在这里插入图片描述][format_png]

## 简单说下这道题目 ##

这道题目就是输入线段树的模板就好了，要注意的地方是：  
1.求区间和的函数，返回值必须是long long类型。  
2.这题必须要用到pushdowm操作，pushdowm是线段树的魅力所在，如果没有用到pushdowm，它的操作数是暴力操作的4-5倍，所以如果是最初的线段树，那它还不如暴力，做这道题目绝对会超时。  
通过这道题目，我发现了自己的错误，对于区间求和和区间修改，都需要pushdowm操作。

代码如下：

#include<algorithm>
    #include<cstring>
    #include<string>
    #include<iostream>
    using namespace std;
    #define ll long long
    typedef struct
    {
        
        ll l,r,w,lazy=0;
    } NODE;
    NODE tree[400005];
    int build(ll l,ll r,ll k)
    {
        
        tree[k].l=l;
        tree[k].r=r;
        if(l==r)
        {
        
            cin>>tree[k].w;
            return 0;
        }
        else
        {
        
            ll mid;
            mid=l+(r-l)/2;
            build(l,mid,k<<1);
            build(mid+1,r,k<<1|1);
            tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
        }
    }
    void pushdowm(int k)
    {
        
        if(tree[k].l==tree[k].r)
        {
        
            tree[k].lazy=0;
            return ;
        }
        tree[k<<1].w+=(tree[k<<1].r-tree[k<<1].l+1)*tree[k].lazy;
        tree[k<<1|1].w+=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k].lazy;
        tree[k<<1].lazy+=tree[k].lazy;
        tree[k<<1|1].lazy+=tree[k].lazy;
        tree[k].lazy=0;
    }
    ll ask_interval(ll x,ll y,ll k)
    {
        
        if(tree[k].lazy)
            pushdowm(k);
        if(tree[k].l==x&&tree[k].r==y)
            return tree[k].w;
        ll mid=tree[k].l+(tree[k].r-tree[k].l)/2;
        if(mid>=y)
            return ask_interval(x,y,k<<1);
        if(x>mid)
            return ask_interval(x,y,k<<1|1);
        return ask_interval(x,mid,k<<1)+ask_interval(mid+1,y,k<<1|1);
    }
    void add(int k,int x,int y,int t)
    {
        
        if(tree[k].l==x&&tree[k].r==y)
        {
        
            tree[k].w+=(tree[k].r-tree[k].l+1)*t;
            tree[k].lazy+=t;
            return ;
        }
            if(tree[k].lazy)
            pushdowm(k);
        ll mid=tree[k].l+(tree[k].r-tree[k].l)/2;
        if(y<=mid)
            add(k<<1,x,y,t);
        else if(x>mid)
            add(k<<1|1,x,y,t);
        else
        {
        
            add(k<<1,x,mid,t);
            add(k<<1|1,mid+1,y,t);
        }
        tree[k].w=tree[k<<1].w+tree[k<<1|1].w;
    }
    int main()
    {
        
        int n,m;
        cin>>n>>m;
        build(1,n,1);
        for(int i=1; i<=m; i++)
        {
        
            int flag,a,b,k;
            cin>>flag>>a>>b;
            if(flag==2)
            {
        
                ll ans=0;
                ans=ask_interval(a,b,1);
                cout<<ans<<endl;
            }
            else if(flag==1)
            {
        
                cin>>k;
                add(1,a,b,k);
            }
        }
        return 0;
    }

[format_png]: /images/20230528/22c1d9cebe3d4daba57f32a493d5104d.png