Дерево отрезков на максимальный подотрезок-сумму (maximum subarray) — как сливать узлы?

В узле храните 4 величины для его подотрезка: sum (вся сумма), pref (максимальный префиксный подотрезок), suf (максимальный суффиксный), best (максимальный подотрезок целиком внутри). Это классический «merge структуры», и именно слияние — суть задачи.

struct Node {
    long long sum, pref, suf, best;
};
Node merge(const Node& a, const Node& b) {
    Node r;
    r.sum  = a.sum + b.sum;
    r.pref = max(a.pref, a.sum + b.pref);
    r.suf  = max(b.suf, b.sum + a.suf);
    r.best = max({a.best, b.best, a.suf + b.pref});
    return r;
}
Node leaf(long long x) {
    // если разрешён пустой подотрезок -> max(x, 0); иначе x
    return {x, x, x, x};
}

Ключ — r.best = max(a.best, b.best, a.suf + b.pref): лучший подотрезок либо целиком слева, либо целиком справа, либо пересекает границу детей (суффикс левого + префикс правого). Префикс/суффикс родителя тоже учитывают, что они могут протянуться через всего ребёнка.

build O(n), точечное обновление O(log n), запрос O(log n). При запросе на [l, r] сливайте Node-ответы канонических узлов в правильном порядке (слева направо!) — операция некоммутативна.