CSES – Subarray Sum Queries

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