新手学线段树,求助

P3372 【模板】线段树 1

lcy_123 @ 2023-04-15 16:21:46

敲了一下午键盘,没找到问题在哪,样例都过不了 (注释可能有点问题...)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[200005],lazy_tag[200005],ans[200005];
inline int read()//快读 
{
    register int s=0,w=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            w=-1; 
            ch=getchar();
        }
    }
    while(ch>='0'&&ch<='9')
    {
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int ls(int x)//当前节点左儿子编号:2*x 
{
    return x/2;
}
int rs(int x)//当前节点右儿子编号:2*x+1 
{
    return x/2+1;
}
void push_up(int pos)//节点回溯,答案记录为左右儿子之和 
{
    ans[pos]=ans[ls(pos)]+ans[rs(pos)];
}
void build(int l,int r,int pos)//建树 
{
    lazy_tag[pos]=0;
    if(l==r)//左右儿子相同,为叶子节点,赋值 
    {
        ans[pos]=a[l];
        return;
    }
    int mid=(l+r)/2;//二分向下搜索叶子节点 
    build(l,mid,ls(pos));//左边:l~mid 
    build(mid+1,r,rs(pos));//右边:mid+1~r 
    push_up(pos);//回溯,进行答案的维护 
}
void sum(int pos,int l,int r,int add)//记录当前节点所代表的区间 
{
    ans[pos]+=add*(r-l+1);//改变整个区间,加上元素个数个值 
    lazy_tag[pos]+=add; 
}
void push_down(int pos,int l,int r)
{
    int mid=(l+r)/2;//二分记录两边子节点 
    sum(ls(pos),l,mid,lazy_tag[pos]);//左儿子 
    sum(rs(pos),mid+1,r,lazy_tag[pos]);//右儿子 
    lazy_tag[pos]=0;
}
void update(int dl,int dr,int l,int r,int pos,int add)//区间修改 
{
    //dl,dr为修改区间,add是修改的值 
    if(dl<=l&&r<=dr)//当前区间整个在修改区间内,修改整个区间 
    {
        ans[pos]+=add*(r-l+1);//和sum函数内一样 
        lazy_tag[pos]+=add;
        return ;
    }
    push_down(pos,l,r);//向下传导lazy_tag 
    int mid=(l+r)/2;//二分往左右儿子传导 
    if(dl<=mid)update(dl,dr,l,mid,ls(pos),add);//左边 
    if(dr>mid)update(dl,dr,mid+1,r,rs(pos),add);//右边 
    push_up(pos);//向上回溯 
}
int ask(int dl,int dr,int l,int r,int pos)//区间询问 
{
    //dl,dr为询问区间 
    int tot=0;//询问的答案 
    if(dl<=l&&r<=dr)return ans[pos];//当前区间整个在询问区间内,返回整个区间的答案 
    push_down(pos,l,r);//将lazy_tag向下传导完 
    int mid=(l+r)/2;//左右查找区间 
    if(dl<=mid)tot+=ask(dl,dr,l,mid,ls(pos));//左边,答案累加 
    if(dr>mid)tot+=ask(dl,dr,mid+1,r,rs(pos));//右边,答案累加 
    return tot;
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int b=read();
        if(b==1)
        {
            int x=read(),y=read(),add=read();
            update(x,y,1,n,1,add);
        }
        else
        {
            int x=read(),y=read();
            cout<<ask(x,y,1,n,1)<<endl;
        }
    }
}

by piasticOuO @ 2023-04-15 16:37:58

子节点应该是*2而不是/2吧?


by lcy_123 @ 2023-04-15 16:40:05

@piasticOuO 哦哦哦,注释都写了打错了,眼睛是真的花了,谢谢dalao

awa


|