Узел сложнее числа

Если ответ для склейки не считается из ответов частей, узел выбран слишком бедным. Почти все интересные задачи на дерево отрезков решаются его расширением.

Приём один и тот же: в узел кладут то, чего не хватает для склейки. Ниже три классических примера, и каждый стоит один раз вывести самому.

Минимум и количество минимумов

Узел — пара «значение, сколько раз встречается».

Node merge(Node a, Node b) {
    if (a.value < b.value) return a;
    if (b.value < a.value) return b;
    return {a.value, a.count + b.count};
}

Три ветки, и третья — та, ради которой задача существует. Версия return a.value <= b.value ? a : b собирается, проходит примеры и ломается на массиве из одинаковых чисел.

Нейтральный элемент — $(+\infty, 0)$. Не $(+\infty, 1)$: единица просочится в счётчик.

Максимальная сумма подотрезка

Разговор с собой, который стоит проделать целиком:

• храню только ответ → склеить не могу: лучший подотрезок может пересекать границу;
• добавлю лучший суффикс левого и лучший префикс правого → ответ склейки считается;
• но сам префикс склейки надо пересчитать: он либо внутри левого, либо это весь левый плюс префикс правого — нужна сумма левого;
• итог: четыре числа.

Node merge(Node a, Node b) {
    Node c;
    c.sum = a.sum + b.sum;
    c.prefix = std::max(a.prefix, a.sum + b.prefix);
    c.suffix = std::max(b.suffix, b.sum + a.suffix);
    c.best = std::max({a.best, b.best, a.suffix + b.prefix});
    return c;
}

Решите заранее, разрешён ли пустой подотрезок. Если да — все четыре величины начинаются с нуля и никогда не отрицательны. Если нет — лист хранит само число, каким бы отрицательным оно ни было, и на массиве из отрицательных ответ равен наибольшему из них.

Проверено перебором: 20 000 случайных массивов длины до 12, обе версии — сорок тысяч сверок с полным перебором подотрезков, расхождений нет.

Самая длинная серия нулей

Узел — длина отрезка и три величины: серия в начале, в конце и вообще.

Node merge(Node a, Node b) {
    Node c;
    c.len = a.len + b.len;
    c.prefix = a.prefix == a.len ? a.len + b.prefix : a.prefix;
    c.suffix = b.suffix == b.len ? b.len + a.suffix : b.suffix;
    c.best = std::max({a.best, b.best, a.suffix + b.prefix});
    return c;
}

Сравните с предыдущим примером. Там префикс склейки считался через максимум, здесь — через проверку на полноту: серия продолжается в правый отрезок, только если левый целиком из нулей.

Длина в узле лежит именно ради этой проверки. Обратная проверка: если поле никогда не участвует в merge и не является ответом, оно лишнее.

Общее правило

Составной узел выводится, а не вспоминается. Возьмите два отрезка, попробуйте склеить, и там, где не хватит информации, — добавьте поле.