MnZn不会线段树，10pts求条

ljcnoi @ 2024-12-15 10:07:00

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long int a[100005],tree[400005],tag[400005];
long long int k;
int d,x,y;
void build(int l,int r,int x)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        build(l,mid,x*2);
        build(mid+1,r,x*2+1);
    }
    if(l==r)
    {
        tree[x]=a[l];
    }
    else
    {
        tree[x]=tree[x*2]+tree[x*2+1];
    }
}
void pushdown(int l,int r,int x)
{
    if(tag[x])
    {
        int mid=(l+r)/2;
        tag[x*2]+=tag[x];
        tree[x*2]+=(mid-l+1)*tag[x];
        tag[x*2+1]+=tag[x];
        tree[x*2+1]+=(mid-l+1)*tag[x];
    }
    tree[x]=tree[x*2]+tree[x*2+1];
}
void update(int l,int r,long long int d,int ll,int rr,int x)
{
    if(l<=ll&&r>=rr)
    {
        tag[x]+=d;
        tree[x]+=(ll-rr+1)*d;
    }
    else
    {
        pushdown(ll,rr,x);
        int mid=(ll+rr)/2;
        if(l<=mid)
        {
            update(l,r,d,ll,mid,x*2);
        }
        if(r>mid)
        {
            update(l,r,d,mid+1,rr,x*2+1);
        }
        tree[x]=tree[x*2]+tree[x*2+1];
    }
}
long long int query(int l,int r,int ll,int rr,int x)
{
    if(l<=ll&&rr<=r)
    {
        return tree[x];
    }
    pushdown(ll,rr,x);
    int mid=(ll+rr)/2;
    long long int ans=0;
    if(l<=mid)
    {
        ans+=query(l,r,ll,mid,x*2);
    }
    if(r>mid)
    {
        ans+=query(l,r,mid+1,rr,x*2+1);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&d);
        if(d==2)
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(x,y,1,n,1));
        }
        else
        {
            scanf("%d%d%lld",&x,&y,&k);
            update(x,y,k,1,n,1);
        }
    }
    return 0;
}

by Polarisx @ 2024-12-15 10:26:38

@ljcnoi

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long int a[100005],tree[400005],tag[400005];
long long int k;
int d,x,y;
void build(int l,int r,int x)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        build(l,mid,x*2);
        build(mid+1,r,x*2+1);
    }
    if(l==r)
    {
        tree[x]=a[l];
    }
    else
    {
        tree[x]=tree[x*2]+tree[x*2+1];
    }
}
void pushdown(int l,int r,int x)
{
    if(tag[x])
    {
        int mid=(l+r)/2;
        tag[x*2]+=tag[x];
        tree[x*2]+=(mid-l+1)*tag[x];
        tag[x*2+1]+=tag[x];
        tree[x*2+1]+=(r-mid)*tag[x];
        tag[x]=0;
    }
    tree[x]=tree[x*2]+tree[x*2+1];
}
void update(int l,int r,long long int d,int ll,int rr,int x)
{
    if(l<=ll&&r>=rr)
    {
        tag[x]+=d;
        tree[x]+=1ll*(rr-ll+1)*d;
    }
    else
    {
        pushdown(ll,rr,x);
        int mid=(ll+rr)/2;
        if(l<=mid)
        {
            update(l,r,d,ll,mid,x*2);
        }
        if(r>mid)
        {
            update(l,r,d,mid+1,rr,x*2+1);
        }
        tree[x]=tree[x*2]+tree[x*2+1];
    }
}
long long int query(int l,int r,int ll,int rr,int x)
{
    if(l<=ll&&rr<=r)
    {
        return tree[x];
    }
    pushdown(ll,rr,x);
    int mid=(ll+rr)/2;
    long long int ans=0;
    if(l<=mid)
    {
        ans+=query(l,r,ll,mid,x*2);
    }
    if(r>mid)
    {
        ans+=query(l,r,mid+1,rr,x*2+1);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&d);
        if(d==2)
        {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(x,y,1,n,1));
        }
        else
        {
            scanf("%d%d%lld",&x,&y,&k);
            update(x,y,k,1,n,1);
        }
    }
    system("pause");
    return 0;

}

by Genius_Star @ 2024-12-15 10:34:25

@ljcnoi 注意：

• 下传了标记后要加懒标记清空。

by ljcnoi @ 2024-12-15 10:38:01

@Genius_Star@Polarisx
谢谢，已过，能推荐几道练习线段树的板子吗？

by litjohn @ 2024-12-15 10:41:50

@ljcnoi 3373