【数据结构】线段树2

在线段树1中,实现了区间最大值,现在这里实现区间最小值,区间和,应该不涉及区间修改。
这里在结构体中增加变量来维护区间最大值$max$,区间最小值$min$,区间和$sum$。

class SegmentTree{
    public:int l,r;
    public:int max,min,sum;
}
SegmentTree t[MAXN * 4];

inline int max(int a,int b){return a > b ? a : b;}
inline int LEFT(int x){return x << 1;}
inline int RIGHT(int x){return x << 1 | 1;}
inline int MID(int l,int r){return (l + r) >> 1;}

每次需要维护上述信息,为了方便调用,写成一个函数。

void maintain(int p){
    t[p].max = max(t[LEFT(p)].max,t[RIGHT(p)].max);
    t[p].min = min(t[LEFT(p)].min,t[RIGHT(p)].min);
    t[p].sum = t[LEFT(p)].sum + t[RIGHT(p)].sum;
}

建树也进行一点修改

void build(int p,int l,int r){
    t[p].l = l;t[p].r = r;
    if(l == r){
        t[p].max = t[p].min = t[p].sum = a[l];
        return;
    }
    build(LEFT(p),l,MID(l,r));
    build(RIGHT(p),MID(l,r) + 1,r);
    maintain(p);
}

单点修改

void change(int p,int x,int v){
    if(t[p].l == t[p].r){
        t[p].max = t[p].min = t[p].sum = v;
        return;
    }
    if(x <= MID(t[p].l,t[p].r)){
        change(LEFT(p),x,v);
    }else{
        change(RIGHT(p),x,v);
    }
    maintain(p);
}

区间查询

SegmentTree ask(int p,int l,int r){
    if(l <= t[p].l && r >= t[p].r){
        return t[p];
    }
    SegmentTree ans;
    ans.max = -0x7fffffff;
    ans.min = 0x7fffffff;
    ans.sum = 0;
    if(l <= MID(t[p].l,t[p].r)){
        ans.max = max(ans.max,ask(LEFT(p),l,r).max);
        ans.min = min(ans.min,ask(LEFT(p),l,r).min);
        ans.sum += ask(LEFT(p),l,r).sum;
    }
    if(r > MID(t[p].l,t[p].r)){
        ans.max = max(ans.max,ask(RIGHT(p),l,r).max);
        ans.min = min(ans.min,ask(RIGHT(p),l,r).min);
        ans.sum += ask(RIGHT(p),l,r).sum;
    }
    return ans;
}