有巨佬能帮忙解释一下吗?

P3372 【模板】线段树 1

IAKIOI66666 @ 2024-07-12 11:28:23

以下是老师的代码 绝非抄题解,根本搞不懂 down 函数 小学五年级智力有限 ,请懂的巨佬帮忙解释一下。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
long long a[101000]; 
struct node{
    int l,r;
    long long dat,add;
}tree[401000];
void build(int p,int l,int r)
{
    tree[p].l=l,tree[p].r=r;
    if(l==r){tree[p].dat=a[l];return;}
    int x=p*2,y=p*2+1;
    int mid=(l+r)/2;
    build(x,l,mid);
    build(y,mid+1,r);
    tree[p].dat=tree[x].dat+tree[y].dat; 
}
void down(int p)
{
    int d=tree[p].add;
    int x=p*2,y=p*2+1;
    tree[x].dat+=d*(tree[x].r-tree[x].l+1);
    tree[x].add+=d;
    tree[y].dat+=d*(tree[y].r-tree[y].l+1);
    tree[y].add+=d;
    tree[p].add=0;
}
void update(int p,int l,int r,long long k)
{
    if(tree[p].l>=l&&tree[p].r<=r)
    {
        tree[p].dat+=k*(tree[p].r-tree[p].l+1);
        tree[p].add+=k;
        return;
    }
    down(p);
    int x=p*2,y=p*2+1;
    int mid=(tree[p].l+tree[p].r)/2;
    if(l<=mid)update(x,l,r,k);
    if(r>mid)update(y,l,r,k);
    tree[p].dat=tree[x].dat+tree[y].dat;
}
long long  ask(int p,int l,int r)
{
    if(tree[p].l>=l&&tree[p].r<=r)return tree[p].dat;
    down(p);
    int x=p*2,y=p*2+1;
    int mid=(tree[p].l+tree[p].r)/2;
    long long ans=0;
    if(l<=mid)ans+=ask(x,l,r);
    if(r>mid)ans+=ask(y,l,r);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    int l,r,t; long long k;
    while(m--)
    {
        scanf("%d",&t);
        if(t==1)
        {
            scanf("%d%d%lld",&l,&r,&k);
            update(1,l,r,k);
        }
        else
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",ask(1,l,r));
        }
    }
    return 0;
}

麻烦了,谢谢。


by Kotobuki_Tsumugi @ 2024-07-12 11:38:24

好吧我理解错了。。


by Kotobuki_Tsumugi @ 2024-07-12 11:38:42

down函数就是把标记下放啊


by IAKIOI66666 @ 2024-07-12 11:40:11

?????

算了,我还是问老师吧


by Kotobuki_Tsumugi @ 2024-07-12 11:40:23

标记的含义是:当前节点的子节点需要更新。所以在修改、查询时遍历每一个节点时都要把标记再传给子节点。


by chaynflow @ 2024-07-12 11:53:10

@IAKIOI66666 orz 小五学线段树


by Alpha1115 @ 2024-07-13 13:47:58

俺也一样(xxs五年级 )


|