【テンプレート】線分樹_区間の最大値、区間の合計、修正

#include 
#include 
#include 
#include 
#define L(x) (x << 1)//   
#define R(x) (x << 1 | 1)//   
#define sz(x) (tree[x].r - tree[x].l + 1)//    
using namespace std;
typedef long long ll;
const ll MAXN = 200005;
ll n,m,a,b,c,num[MAXN];
string t;
// l ==  ；r ==  ；p == now;
struct tree{
    ll l,r,add,sum;//    
    ll min,max;//    
}tree[MAXN << 2];

//      p == now
void update(ll p){
    tree[p].sum = tree[L(p)].sum + tree[R(p)].sum;
    tree[p].max = max(tree[L(p)].max,tree[R(p)].max);
    tree[p].min = min(tree[L(p)].min,tree[R(p)].min);
}

void spread(ll p){
    if(!tree[p].add)    return;
    tree[L(p)].max += tree[p].add;
    tree[R(p)].max += tree[p].add;
    tree[L(p)].min += tree[p].add;
    tree[R(p)].min += tree[p].add;

    tree[L(p)].add += tree[p].add;
    tree[R(p)].add += tree[p].add;
    tree[L(p)].sum += tree[p].add * sz(L(p));
    tree[R(p)].sum += tree[p].add * sz(R(p));
    tree[p].add = 0;//!!!!!!!
    update(p);
}

//     
void build(ll l,ll r,ll p){
    tree[p].l = l,tree[p].r = r;
    if(l == r){
        tree[p].min = tree[p].max = tree[p].sum = num[l];
        return;
    }
    ll mid = (tree[p].l + tree[p].r) >> 1;
    build(l,mid,L(p));  build(mid + 1,r,R(p));
    update(p);
}

//    
void change(ll l,ll r,ll p,ll v){
    if(l <= tree[p].l && tree[p].r <= r){
        tree[p].add += v;
        tree[p].min += v;
        tree[p].max += v;
        tree[p].sum += v * sz(p);
        return;
    }
    spread(p);
    ll mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid) change(l,r,L(p),v);
    if(mid < r) change(l,r,R(p),v);
    update(p);
}

//    
ll ask_sum(ll l,ll r,ll p){
    if(l <= tree[p].l && tree[p].r <= r)
        return tree[p].sum;
    spread(p);
    ll ans = 0,mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid) ans += ask_sum(l,r,L(p));
    if(mid < r) ans += ask_sum(l,r,R(p));
    update(p);  return ans;
}

//     
ll ask_max(ll l,ll r,ll p){
    if(l <= tree[p].l && tree[p].r <= r)
        return tree[p].max;
    spread(p);
    ll ans = 0,mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid)    ans = max(ans,ask_max(l,r,L(p)));
    if(mid < r)     ans = max(ans,ask_max(l,r,R(p)));
    update(p);      return ans;
}

//     
ll ask_min(ll l,ll r,ll p){
    if(l <= tree[p].l && tree[p].r <= r)
        return tree[p].min;
    spread(p);
    ll ans = 2333333,mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid)    ans = min(ans,ask_min(l,r,L(p)));
    if(mid < r)     ans = min(ans,ask_min(l,r,R(p)));
    update(p);      return ans;
}

int main(){
    memset(num,0,sizeof(num));
    scanf("%lld",&n);
    for(ll i = 1; i <= n; i ++)
        scanf("%lld",&num[i]);
    build(1,n,1);   scanf("%lld",&m);
    for(ll i = 1; i <= m; i ++){
        cin >> t;
        if(t == "add"){
            scanf("%lld %lld %lld",&a,&b,&c);
            change(a,b,1,c);
        }
        else if(t == "sum"){
            scanf("%lld %lld",&a,&b);
            printf("%lld
",ask_sum(a,b,1));
        }
        else if(t == "max"){
            scanf("%lld %lld",&a,&b);
            printf("%lld
",ask_max(a,b,1));
        }
        else if(t == "min"){
            scanf("%lld %lld",&a,&b);
            printf("%lld
",ask_min(a,b,1));
        }
    }
    return 0;
}