Persistent Segment Tree

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Node {
    ll val, pref;
    Node *L, *R;
    Node(ll v = 0) : val(v), pref(max(0LL, v)), L(this), R(this) {}
    Node(ll v, ll p, Node* l, Node* r) : val(v), pref(p), L(l), R(r) {}
};

Node* merge(Node* a, Node* b) {
    return new Node(a->val + b->val, max(a->pref, a->val + b->pref), a, b);
}

const int MAXV = 2e5 + 5;
Node* roots[MAXV];
int N;
ll Lx, Rx;

void init(int n, ll lx = 1, ll rx = -1) {
    N = n; Lx = lx; Rx = (rx < lx ? n : rx);
    for (int i = 0; i <= n; i++) roots[i] = new Node();
}

Node* build(ll a[], ll l, ll r) {
    if (l == r) return new Node(a[l]);
    ll mid = l + (r - l) / 2;
    return merge(build(a, l, mid), build(a, mid + 1, r));
}

void build(ll a[]) { roots[0] = build(a, Lx, Rx); }

Node* update(Node* nd, ll pos, ll val, ll lx, ll rx) {
    if (pos < lx || pos > rx) return nd;
    if (lx == rx) return new Node(val);
    ll mid = lx + (rx - lx) / 2;
    Node* l = update(nd->L, pos, val, lx, mid);
    Node* r = update(nd->R, pos, val, mid + 1, rx);
    return merge(l, r);
}

void insert(ll pos, ll val, int cur, int prev) {
    roots[cur] = update(roots[prev], pos, val, Lx, Rx);
}

void update(ll pos, ll val, int cur) {
    roots[cur] = update(roots[cur], pos, val, Lx, Rx);
}

Node* query(Node* nd, ll l, ll r, ll lx, ll rx) {
    if (!nd || lx > r || rx < l) return new Node();
    if (lx >= l && rx <= r) return nd;
    ll mid = (lx + rx) / 2;
    return merge(query(nd->L, l, r, lx, mid), query(nd->R, l, r, mid + 1, rx));
}

ll query(ll l, ll r, int t) { return query(roots[t], l, r, Lx, Rx)->pref; }