线段树板子（结构体版）

#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
struct segtree{
    struct node {
        int l,r;
        int sum,mn,mx;
        int tag;
    };
    int n;
    const int inf=1e9;
    vector<int> a;
    vector<node> t;
    segtree(int x){
        n=x;
        a.resize(n+1);
        t.resize((n+1)<<2);
        build(1,1,n);
    }
    segtree(int x,vector<int> &v){
        n=x;
        a=v;
        t.resize((n+1)<<2);
        build(1,1,n);
    }
    void push_up(int p){
        t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
        t[p].mn=min(t[ls(p)].mn,t[rs(p)].mn);
        t[p].mx=max(t[ls(p)].mx,t[rs(p)].mx);
    }
    void build(int p,int l,int r){
        if(l==r){
            t[p]={l,r,a[l],a[l],a[l],0};
            return;
        }
        t[p]={l,r};
        int mid=(l+r)>>1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        push_up(p);
    }
    void addtag(int p,int d){
        t[p].tag+=d;
        t[p].sum+=(t[p].r-t[p].l+1)*d;
        t[p].mn+=d;
        t[p].mx+=d;
    }
    void push_down(int p){
        if(t[p].tag){
            addtag(ls(p),t[p].tag);
            addtag(rs(p),t[p].tag);
            t[p].tag=0;
        }
    }
    void update(int l,int r,int p,int d){
        if(l<=t[p].l&&t[p].r<=r){
            addtag(p,d);
            return;
        }
        push_down(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid) update(l,r,ls(p),d);
        if(mid<r) update(l,r,rs(p),d);
        push_up(p);
    }
    ll query_sum(int l,int r,int p){
        if(l<=t[p].l&&t[p].r<=r){
            return t[p].sum;
        }
        push_down(p);
        int ans=0;
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid) ans+=query_sum(l,r,ls(p));
        if(mid<r) ans+=query_sum(l,r,rs(p));
        return ans;
    }
    ll query_mn(int l,int r,int p){
        if(l<=t[p].l&&t[p].r<=r){
            return t[p].mn;
        }
        push_down(p);
        ll ans=inf;
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid) ans=min(ans,query_mn(l,r,ls(p)));
        if(mid<r) ans=min(ans,query_mn(l,r,rs(p)));
        return ans;
    }
    ll query_mx(int l,int r,int p){
        if(l<=t[p].l&&t[p].r<=r){
            return t[p].mx;
        }
        push_down(p);
        ll ans=-inf;
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid) ans=max(ans,query_mx(l,r,ls(p)));
        if(mid<r) ans=max(ans,query_mx(l,r,rs(p)));
        return ans;
    }
};