关于分块
  • 板块学术版
  • 楼主_lqs_
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/4/30 13:47
  • 上次更新2023/10/23 17:09:45
查看原帖
关于分块
664744
_lqs_楼主2023/4/30 13:47
void update(int l,int r,int k){
	int s=w[l],t=w[r];
	if(s==t){
		for(int i=l;i<=r;i++) a[i]+=k,b[s]+=k;
		return;
	}
	for(int i=l;w[i]==s;i++) a[i]+=k,b[s]+=k;
	for(int i=r;w[i]==t;i--) a[i]+=k,b[t]+=k;
	for(int i=s+1;i<=t-1;i++) delta[i]+=k,b[i]+=(siz[i]*k);
	return;
}
int query(int l,int r){
	int s=w[l],t=w[r],sum=0;
	if(s==t){
		for(int i=l;i<=r;i++) sum+=a[i]+delta[s];
		return sum;
	}
	for(int i=l;w[i]==s;i++) sum+=(a[i]+delta[w[i]]);
	for(int i=r;w[i]==t;i--) sum+=(a[i]+delta[w[i]]);
	for(int i=s+1;i<=t-1;i++) sum+=b[i];
	return sum;
}

拿线段树模板 1 为例,以上是修改和查询的分块代码,想问 for(int i=s+1;i<=t-1;i++) sum+=b[i]; 这个地方为什么不用加上一整段的标记?请大佬解答,谢谢。

2023/4/30 13:47
加载中...