线段树模板（区间更新，区间求和，区间最值）

线段树模板

#include <iostream>
#include <stdio.h>
#define ll long long
#define lson  rt << 1
#define rson  rt << 1 | 1
#define il inline
using namespace std;
const ll MAXN = 1e5 + 10;
struct Tree {//定义结构
        ll l,r;//节点左右端点
        ll sum;//求和 
        ll lazy;//延迟标记
        ll maxn;//最大值 
        ll minn;// 最小值 
} t[MAXN<<2];//开4倍空间
il void push_up(ll rt) { //向上更新
    t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum;//更新和
    t[rt].maxn = max(t[rt << 1].maxn ,t[rt << 1 | 1].maxn);//更新最大值
    t[rt].minn = min(t[rt << 1].minn ,t[rt << 1 | 1].minn);//更新最小值
}
il void push_down(ll rt, ll m) {//pushdown函数
    if(t[rt].lazy) { //若有标记,则将标记向下移动一层
        t[rt << 1].lazy += t[rt].lazy;
        t[rt << 1 | 1].lazy += t[rt].lazy;
        t[rt << 1].sum += (m - (m >> 1)) * t[rt].lazy;
        t[rt << 1 | 1].sum += (m >> 1) * t[rt].lazy;
        t[rt << 1].minn += t[rt].lazy;
        t[rt << 1 | 1].minn+= t[rt].lazy;
        t[rt << 1].maxn += t[rt].lazy;
        t[rt << 1 | 1].maxn+= t[rt].lazy;
        t[rt].lazy = 0;//取消本层标记
    }
}
il void build(ll l,ll r, ll rt) { //建树
    t[rt].lazy = 0;
    t[rt].l=l;
    t[rt].r=r;
    if(l == r) {
        scanf("%lld",&t[rt].sum);
        t[rt].minn=t[rt].sum;
        t[rt].maxn=t[rt].sum;
        return;
    }
    ll mid = (l + r) >> 1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);//向上更新
}
il void update(ll L,ll R, ll key, ll rt) { //区间更新
    if(L <= t[rt].l && R >= t[rt].r) {
        t[rt].sum+=(t[rt].r - t[rt].l + 1) * key;
        t[rt].minn+=key;
        t[rt].maxn+=key;
        t[rt].lazy+=key;
        return;
    }
    push_down(rt, t[rt].r - t[rt].l + 1);//向下更新
    ll mid = (t[rt].r + t[rt].l) >> 1;
    if(L <= mid) update(L, R, key, lson);
    if(R > mid) update(L, R, key, rson);
    push_up(rt);//向上更新
}
il ll query(ll L, ll R, ll rt) { //区间求和
    if(L <= t[rt].l && R >= t[rt].r) {
        return t[rt].sum;
    }
    push_down(rt, t[rt].r - t[rt].l + 1);//向下更新
    ll mid = (t[rt].r + t[rt].l) >> 1;
    ll ans = 0;
    if(L <= mid) ans += query(L, R, lson);
    if(R > mid) ans += query(L, R, rson);
    return ans;
}
il ll query_min(ll L, ll R, ll rt) { //区间求最小值
    if(L <= t[rt].l && R >= t[rt].r) {
        return t[rt].minn;
    }
    push_down(rt, t[rt].r - t[rt].l + 1);//向下更新
    ll mid = (t[rt].r + t[rt].l) >> 1;
    ll ans = 0x3f3f3f3f;
    if(L <= mid) ans = min(ans,query_min(L, R, lson));
    if(R > mid) ans =min(ans,query_min(L, R, rson)) ;
    return ans;
}
il ll query_max(ll L, ll R, ll rt) { //区间求最大值
    if(L <= t[rt].l && R >= t[rt].r) {
        return t[rt].maxn;
    }
    push_down(rt, t[rt].r - t[rt].l + 1);//向下更新
    ll mid = (t[rt].r + t[rt].l) >> 1;
    ll ans = 0;
    if(L <= mid) ans = max(ans,query_max(L, R, lson));
    if(R > mid) ans = max(ans,query_max(L, R, rson));
    return ans;
}
int main() {
    ll n,l,r,v;
    char a;
    int t;
    cin>>t;
    for(ll i=1; i<=t; i++) {
        scanf("%lld", &n);
        build(1, n, 1);
        while(cin>>a&&a!='e') {
            if(a=='a') {
                scanf("%lld%lld%lld",&l,&r,&v);
                update(l,r,v,1);
            } else if(a=='s') {
                scanf("%lld%lld",&l,&r);
                printf("%lld\n",query(l,r,1));
            } else if(a=='m') {
                scanf("%lld%lld",&l,&r);
                printf("%lld\n",query_min(l,r,1));
            } else {
                scanf("%lld%lld",&l,&r);
                printf("%lld\n",query_max(l,r,1));
            }
        }
    }
    return 0;
}

博主CSDN
博主自己的博客网站