求助,为什么线段树两种写法结果不一样
查看原帖
求助,为什么线段树两种写法结果不一样
927832
FLORIZ楼主2023/7/29 18:52

三个查询的函数(以查 sumsum 的为例),如果是这么写

inline long long asksum(long long hao,long long l,long long r)
	{if(shu[hao].l>=l && shu[hao].r<=r)	
		{return shu[hao].sum;
		}
	pushdown(hao);
	int mid=(shu[hao].l+shu[hao].r)>>1;
	int val=0;
	if(l<=mid) val+=asksum(lc,l,r); 
	if(r>mid) val+=asksum(rc,l,r);
	return val; 
	}

就只能A一个点

如果是

inline long long asksum(long long hao,long long l,long long r)
	{if(l>shu[hao].r || r<shu[hao].l) return 0;
	if(shu[hao].l>=l && shu[hao].r<=r)	
		{return shu[hao].sum;
		}
	pushdown(hao);
	return asksum(rc,l,r)+asksum(lc,l,r); 
	}

就能A

2023/7/29 18:52
加载中...