下面是一个封装好的线段树,用于维护区间加以及区间求最大值。
想问下:
为何线段树内的数组开 4 倍空间会 RE,开 10 倍就没事?
这份代码否存在一些问题?
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;