求问,关于线段树
  • 板块学术版
  • 楼主潘德理2010
  • 当前回复23
  • 已保存回复23
  • 发布时间2024/10/19 17:32
  • 上次更新2024/10/19 19:48:02
查看原帖
求问,关于线段树
572133
潘德理2010楼主2024/10/19 17:32

下面是一个封装好的线段树,用于维护区间加以及区间求最大值。

想问下:

  • 为何线段树内的数组开 44 倍空间会 RE,开 1010 倍就没事?

  • 这份代码否存在一些问题?

struct sgt{
	ll v[2000100],m[2000100],t[2000100];//总和 最大值 加法标记 
	void cl(){
		memset(v,0,sizeof(v));
		memset(m,0,sizeof(v));
		memset(t,0,sizeof(v));
	}
	void push_down(ll u,ll le,ll ri){
		ll x=t[u];
		v[u]+=x*(ri-le+1);
		m[u]+=x;
		t[2*u]+=x;
		t[2*u+1]+=x;
		t[u]=0;
	}
	void push_up(ll u){
		v[u]=v[2*u]+v[2*u+1];
		m[u]=max(m[2*u],m[2*u+1]);
	}
	void add(ll u,ll le,ll ri,ll x,ll y,ll w){//[x,y] 加 w 
		if(x<=le&&ri<=y){
			t[u]+=w;
			push_down(u,le,ri);
			return ;
		}
		push_down(u,le,ri);
		ll mid=(le+ri)/2;
		if(x<=mid) add(2*u,le,mid,x,y,w);
		if(y>mid) add(2*u+1,mid+1,ri,x,y,w);
		push_up(u);
	}
	ll que(ll u,ll le,ll ri,ll x,ll y){//查询 [x,y] 最大值 
		push_down(u,le,ri);
		if(x<=le&&ri<=y){
			return m[u];
		}
		ll mid=(le+ri)/2;
		ll ret=-1<<30;
		if(x<=mid) ret=max(ret,que(2*u,le,mid,x,y));
		if(y>mid) ret=max(ret,que(2*u+1,mid+1,ri,x,y));
		return ret;
	}
}t;
2024/10/19 17:32
加载中...