关于线段树的懒标记
  • 板块学术版
  • 楼主pencil
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/7/20 19:59
  • 上次更新2023/11/4 14:01:48
查看原帖
关于线段树的懒标记
137723
pencil楼主2021/7/20 19:59

直接把标记下放就可以了吗(区间加区间求)

那我这里那里不对呢

void jia(int wz,int z,int y,int zhi){
	if(a[wz].l<z||a[wz].r>y)
	return;
	if(a[wz].l>=z&&a[wz].r<=y){
		a[wz].lz=zhi;
		return;
	}
	int mid=(z+y)/2;
	if(a[wz].l>z&&a[wz*2].r<y)
	jia(wz*2,z,mid,zhi);
	if(a[wz].l<y&&a[wz*2+1].l>z)
	jia(wz*2+1,mid+1,y,zhi);
}
void tui(int wz){
	if(a[wz*2].lz==-1) a[wz*2].lz=a[wz].lz;
	else a[wz*2].lz+=a[wz].lz;
	if(a[wz*2+1].lz==-1) a[wz*2+1].lz=a[wz].lz;
	else a[wz*2+1].lz+=a[wz].lz;
	a[wz].lz=0;
}
int qiu(int wz,int z,int y){
	if(a[wz].r<z&&a[wz].l>y) return 0;
	if(a[wz].r>=z&&a[wz].l<=y){
		if(a[wz].lz==-1)
		return a[wz].sum;
		else
		return a[wz].lz*(a[wz].r-a[wz].l+1)+a[wz].sum;
	} 
	if(a[wz].l==a[wz].r)
	return a[wz].sum;
	tui(wz);
	int mid=(z+y)/2,a1=0,b=0;
	if(a[wz*2].r<=z)
	a1=qiu(wz*2,z,mid);
	if(a[wz*2+1].l>=y)
	b=qiu(wz*2+1,mid+1,y);
	return a1+b;
}
2021/7/20 19:59
加载中...