有关此题的线段树合并做法

P3899 [湖南集训] 更为厉害

Alan_Zhao @ 2021-06-27 19:55:32

题解里的线段树合并全都长这样:

int merge(int x,int y,int tl,int tr) {
    if(x==0||y==0) return x|y;
    if(tl==tr) {
        int now=++tot;
        tree[now].num=tree[x].num+tree[y].num;
        return now;
    }
    int mid=(tl+tr)/2,now=++tot;
    tree[now].ls=merge(tree[x].ls,tree[y].ls,tl,mid);
    tree[now].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr);
    up(now);
    return now;
}

或这样:

int merge(int u,int v,int l,int r)
{
    if(!u||!v)return u|v;
    int mid=l+r>>1,x=++tot;
    t[x].siz=t[u].siz+t[v].siz;
    t[x].lc=merge(t[u].lc,t[v].lc,l, mid );
    t[x].rc=merge(t[u].rc,t[v].rc,mid+1,r);
    return x;
}

它们在有一个点为空的时候,都直接返回了另一个点。这样为啥是对的?感觉父节点进行更新的时候有可能会影响到子节点的线段树。


by Aleph1022 @ 2021-06-27 20:34:28

哦,修改也不用可持久化,只要你先修改一遍再合并就行


by Aleph1022 @ 2021-06-27 20:34:40

@Alan_Zhao


by Aleph1022 @ 2021-06-27 20:35:02

就是因为不会影响到线段树上的子结点才不会影响到树上的子结点啊


by Aleph1022 @ 2021-06-27 20:36:46

所以如果你是先 add 完再 merge 就是对的,否则你应当在 add 的时候加入可持久化


by Alan_Zhao @ 2021-06-27 20:40:42

@GuidingStar 差不多明白了,感谢!


上一页 |