DeliPan's blog

By DeliPan, history, 83 minutes ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it