Warning Bells Ringing

Revision en2, by DeliPan, 2026-09-21 17:57:27

If you are writing a segment tree that needs merge,and you need to delete elements,like this:

void del(int &u,int le,int ri,int x,int y){
	// now dealing root u and interval [le,ri]
	// need to delete elements in [x,y]
	if(!u) return;
	if(x<=le&&ri<=y){
		u=0;
		return;
	}
	push_down(u);
	if(x<=mid) del(ls[u],le,mid,x,y);
	if(y>mid) del(rs[u],mid+1,ri,x,y);
	push_up(u);
	if(!ls[u]&&!rs[u]) u=0;// be careful!
}

You may need to clear the empty nodes which without any sons.

If you forget to do this,you may get WA.Because you may query this node later,even it's empty and you didn't know this.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English DeliPan 2026-09-21 17:57:52 79 Reverted to en1
en2 English DeliPan 2026-09-21 17:57:27 79
en1 English DeliPan 2026-09-21 17:53:01 573 Initial revision (published)