线段树区间最值

2019-12-16 / 无评论

修改了一下王佬的线段树模板,现在支持查询区间最大值了,以前只能最小值

#define INF 0x3f3f3f3f
#define lson (o<<1)
#define rson (o<<1|1) 
const int maxn = 1e6+7;
int dat[maxn];      //原始数据 
int minv[maxn<<2];  //线段树
int maxv[maxn<<2];  //最大值
int addv[maxn<<2];  //lazy tag
char s[maxn];
void inline pushdown(int o){
    if(!addv[o])
        return;
    addv[lson]+=addv[o];    //更新孩子的tag信息 
    addv[rson]+=addv[o];
    minv[lson]+=addv[o];    //更新孩子的节点信息 
    minv[rson]+=addv[o];
    maxv[lson]+=addv[o];
    maxv[rson]+=addv[o];
    addv[o]=0;
}
void inline pushup(int o)
{
    minv[o]=min(minv[lson],minv[rson]);
    maxv[o]=max(maxv[lson],maxv[rson]);
}

void inline build(int o,int l,int r)
{
    addv[o]=0;              //初始化tag 
    if(l==r)
    {
        minv[o]=dat[l];
        maxv[o]=dat[l];
        return; 
    }
    int mid = (l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(o);
}
void inline change(int o,int l,int r,int ql,int qr,int v) //(1,1,N) ql,qr是更新区间的范围
{
    if(ql<=l&&qr>=r){
        minv[o]+=v;
        maxv[o]+=v;
        addv[o]+=v;
        return;
    }
    int mid = (l+r)>>1;
    pushdown(o);
    if(ql<=mid)
        change(lson,l,mid,ql,qr,v);
    if(qr>mid)
        change(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
int inline query_min(int o,int l,int r,int ql,int qr)   //查询时传参(1,1,N,_,_) 
{
    if(ql<=l&&qr>=r)    return minv[o];
    int mid = (l+r)>>1;
    int ans = INF;
    pushdown(o);
    if(ql<=mid)
        ans=min(ans,query_min(lson,l,mid,ql,qr));
    if(qr>mid)
        ans=min(ans,query_min(rson,mid+1,r,ql,qr));
    return ans; 
}
int inline query_max(int o,int l,int r,int ql,int qr)   //查询时传参(1,1,N,_,_) 
{
    if(ql<=l&&qr>=r)    return maxv[o];
    int mid = (l+r)>>1;
    int ans = -1;
    pushdown(o);
    if(ql<=mid)
        ans=max(ans,query_max(lson,l,mid,ql,qr));
    if(qr>mid)
        ans=max(ans,query_max(rson,mid+1,r,ql,qr));
    return ans; 
}

无回应:“线段树区间最值”

发表评论

电子邮件地址不会被公开。 必填项已用*标注