← all categories

Segment Tree Max Subarray 6ca7ad01

Segment tree computing the maximum subarray sum (Kadane's) under point updates, via the merge trick: each node tracks sum / best-prefix / best-suffix / best-subarray. T needs operator+ and a very negative sentinel (NEG) with headroom below real value magnitudes.

Time: O(\log n) per operation. tested

content/data-structures/segment-tree-max-subarray.h

template <typename T>
struct MaxSubarrayTree {
    static constexpr T NEG = numeric_limits<T>::lowest() / 2;  // headroom avoids overflow

    struct Data {
        T sum = 0, pref = NEG, suff = NEG, best = NEG;
    };

    int n;
    vector<Data> tree;

    Data leaf(T v) { return {v, v, v, v}; }

    Data comb(const Data &a, const Data &b) {
        Data r;
        r.sum = a.sum + b.sum;
        r.pref = max(a.pref, a.sum + b.pref);
        r.suff = max(b.suff, b.sum + a.suff);
        r.best = max({a.best, b.best, a.suff + b.pref});
        return r;
    }

    MaxSubarrayTree(vector<T> &a) : n(a.size()), tree(2 * n) {
        for (int i = 0; i < n; i++) tree[i + n] = leaf(a[i]);
        for (int i = n - 1; i > 0; i--) tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
    }

    void update(int i, T v) {
        tree[i += n] = leaf(v);
        for (i >>= 1; i > 0; i >>= 1) tree[i] = comb(tree[2 * i], tree[2 * i + 1]);
    }

    T query(int l, int r) {  // inclusive [l, r]; returns the best-subarray-sum
        Data resL, resR;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resL = comb(resL, tree[l++]);
            if (r & 1) resR = comb(tree[--r], resR);
        }
        return comb(resL, resR).best;
    }
};