maximal_sum_segment_tree.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = (int)3e5 + 10;
int a[N];
const int INF = (int)1e18;

class Node{
    public:
    int pref, suff, sum, seg;
    Node(){
        pref = -INF; suff = -INF;
        sum = 0; seg = -INF;
    }
    Node(int pref, int suff, int sum, int seg){
        this->pref = pref;
        this->suff = suff;
        this->sum = sum;
        this->seg = seg;
    }
};

class MaxSumST{
    Node t[4 * N];
    public:
    void build(int node, int l, int r){
        if(l == r){ // it's a fucking leaf!
            t[node] = Node(a[l], a[l], a[l], a[l]);
            return;
        }
        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
        merge(node);
    }
    void update(int node, int l, int r, int i, int val){
        if(l > i || r < i)  return;
        if(l == r){
            t[node] = Node(val, val, val, val);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, i, val);
        update(2 * node + 1, mid + 1, r, i, val);
        merge(node);
    }
    Node msum(int node, int l1, int r1, int l, int r){
        if(l1 > r || r1 < l)    return Node();
        if(l1 >= l && r1 <= r)  return t[node];
        int mid = (l1 + r1) / 2;
        Node left = msum(2 * node, l1, mid, l, r);
        Node right = msum(2 * node + 1, mid + 1, r1, l, r);
        return calculate(left, right);
    }
    int getMax(int n){
        return max(0LL, msum(1, 1, n, 1, n).seg);
    }
    private:
    void merge(int node){
        t[node] = calculate(t[node * 2], t[2 * node + 1]);
    }
    Node calculate(Node left, Node right){
        return Node(max(left.pref, left.sum + right.pref), max(right.suff, right.sum + left.suff
        ), left.sum + right.sum, max(max(left.seg, right.seg), left.suff + right.pref));
    }
};

int32_t main(){
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    MaxSumST seggs;
    seggs.build(1, 1, n);
    cout << seggs.getMax(n) << "\n";
    while(q--){
        int i, val; cin >> i >> val; i++;
        seggs.update(1, 1, n, i, val);
        cout << seggs.getMax(n) << '\n';
    }
    return 0;
}