关于线段树pushdown位置
  • 板块学术版
  • 楼主CAICAIA
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/4/27 19:20
  • 上次更新2023/10/23 17:25:01
查看原帖
关于线段树pushdown位置
704655
CAICAIA楼主2023/4/27 19:20
#include<bits/stdc++.h>
using namespace std;
/*
线段树于题库中升起,
如利剑般驱散黑暗,
洒遍光明,化解迷茫,指引道路,
构筑世界之真理。
线段树好闪,拜谢线段树!
*/
long long n,m;
struct no{
	long long sum;
	long long lazy;
	long long l;
	long long r;
}tree[400400];
long long input[100100]={0};

void build(long long l,long long r,long long i){//建树 
	tree[i].l=l;
	tree[i].r=r;
	if(l==r){
		tree[i].sum=input[l];
		return ;
	}
	long long mid=(l+r)>>1;
	
	build(l,mid,i*2);
	build(mid+1,r,i*2+1);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	return ;
}
void pushdown(long long i){
	tree[i*2].lazy+=tree[i].lazy;
	tree[i*2+1].lazy+=tree[i].lazy;
	
	tree[i*2].sum+=(tree[i*2].r-tree[i*2].l+1)*tree[i].lazy;
	tree[i*2+1].sum+=(tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].lazy;
	
	tree[i].lazy=0;
}
long long search(long long l,long long r,long long i){//区间查询 
	if(l<=tree[i].l&&tree[i].r<=r){
		return tree[i].sum;
	}
	if(r<tree[i].l||tree[i].r<l){
		return 0;
	}
	long long sum=0;
	pushdown(i);
	if(l<=tree[i*2].r){
		sum+=search(l,r,i*2);
	}
	if(tree[i*2+1].l<=r){
		sum+=search(l,r,i*2+1);
	}
	return sum;
}

void add(long long l,long long r,long long i,long long k){//区间修改 


	// 为什么pushdown放此处RE 
	
	 
	if(l<=tree[i].l&&tree[i].r<=r){
		tree[i].lazy+=k;
		tree[i].sum+=(tree[i].r-tree[i].l+1)*k;
		
		//为什么这里不用放pushdown 
		
		 
		return ;
	} 
	if(r<tree[i].l||tree[i].r<l){
		return ;
	}
	pushdown(i);
	if(l<=tree[i*2].r){
		add(l,r,i*2,k);
	}
	if(tree[i*2+1].l<=r){
		add(l,r,i*2+1,k);
	}
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	return ;
}

int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++){
		scanf("%lld",&input[i]);
	}
	long long x,y,a,k;
	build(1,n,1);
	for(long long i=1;i<=m;i++){
		cin>>a;
		if(a==1){
			scanf("%lld%lld%lld",&x,&y,&k);
			add(x,y,1,k);
		}
		else{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",search(x,y,1));
		}
	}
	return 0;
}

我把问题放代码里了 在区间修改里面

2023/4/27 19:20
加载中...