CSES – Prefix Sum Queries

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 2e5+5;
int stptr = 1;
struct seg{
    int L, R;
    int lson, rson;
    int maxpre;
    int sum;
    seg(): maxpre(0), sum(0) {}
    seg(int x): maxpre(x), sum(x){}
} ST[4*maxn];
int n,q;
vector<int> v;
//
seg operator +(seg a, seg b){
    a.maxpre = max(a.maxpre, a.sum+b.maxpre);
    a.sum += b.sum;
    return a;
}
void build(int L,int R,int idx){
    ST[idx].L = L, ST[idx].R = R;
    if(L + 1 == R){
        ST[idx].maxpre = max(0ll,v[L]);
        ST[idx].sum = v[L];
        return;
    }
    int lson = ST[idx].lson = stptr++;
    int rson = ST[idx].rson = stptr++;
    int mid = (L+R) / 2;
    build(L,mid,lson);
    build(mid,R,rson);
    ST[idx].sum = ST[lson].sum + ST[rson].sum;
    ST[idx].maxpre = max({ST[lson].maxpre, ST[lson].sum + ST[rson].maxpre});
}
void modify(int x,int pos,int idx){
    if(ST[idx].L + 1 == ST[idx].R){
        ST[idx].sum = x;
        ST[idx].maxpre = max(0ll,x);
        return;
    }
    int lson = ST[idx].lson;
    int rson = ST[idx].rson;
    int mid = (ST[idx].L + ST[idx].R) / 2;
    if(pos < mid) modify(x,pos,lson);
    else modify(x,pos,rson);
    ST[idx].sum = ST[lson].sum + ST[rson].sum;
    ST[idx].maxpre = max({ST[lson].maxpre, ST[lson].sum + ST[rson].maxpre});
}
seg query(int L,int R,int idx){
    if(ST[idx].L == L && ST[idx].R == R){
        return ST[idx];
    }
    int mid = (ST[idx].L + ST[idx].R) / 2;
    int lson = ST[idx].lson, rson = ST[idx].rson;
    if(R <= mid) return query(L,R,lson);
    else if(L >= mid) return query(L,R,rson);
    else return query(L,mid,lson) + query(mid,R,rson);
}
signed main(){
    fastio;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        v.push_back(x);
    }
    build(0,n,0);
    while(q--){
        int op, a, b;
        cin>>op>>a>>b;
        if(op == 1) modify(b,a-1,0);
        else cout<<query(a-1,b,0).maxpre<<"\n";
    }
    return 0;
}