Ошибки в дереве отрезков

Дерево отрезков ошибается тихо. Оно не падает и не зацикливается — оно выдаёт число, похожее на правду. Ниже места, где это происходит чаще всего.

Размер массива

tree объявлен как 4 * n, но $n$ — это размер после чтения, а массив выделен по константе из условия. Или наоборот: массив выделен по $n$, а запросы приходят по индексам до $n$ включительно.

Проверка: запустить с санитайзерами, -fsanitize=address,undefined. Выход за границу они ловят мгновенно, а без них он проявится как неверный ответ на одном тесте из сорока.

Нейтральный элемент

Для суммы это ноль, для минимума — «плюс бесконечность», а не ноль и не INT_MAX. Ноль в минимуме портит ответ на любом массиве из положительных чисел; INT_MAX переполняется при первом же сложении.

Для составного узла нейтральный элемент нужно вывести, а не угадать: он должен удовлетворять $f(e, x) = x$ для любого $x$.

Типы

Сумма $10^5$ чисел по $10^9$ — это $10^{14}$, и int здесь не годится. Отдельно опасно поле пометки: значение элемента может помещаться в int, а накопленная сумма прибавлений — нет.

Правило простое: всё, что суммируется, — long long; экономия памяти на этом почти никогда не нужна.

Пометка не протолкнута

Забытый push в запросе — самая частая ошибка ленивого дерева. Симптом характерный: первый запрос после изменения верен, второй — нет; или ответ верен, пока запросы не пересекают границ изменённого отрезка.

Второй вариант той же ошибки: push вызван, но после проверки на полное покрытие, а не до спуска.

Пометка применена дважды

Если apply меняет и значение, и пометку, а вызывающий код дополнительно правит значение — изменение удвоится. Или: индексы границ совпали (l - 1 и r - 1 при r - l <= 1), и точечное изменение применилось к одной ячейке два раза.

Правило: пометка меняется ровно в одном месте — внутри apply. Больше нигде.

Пустой отрезок

При $l > r$ функция обязана вернуть нейтральный элемент, а не уйти в рекурсию. Такой запрос возникает сам собой: в массиве разностей отрезок $[l, r-1]$ пуст при $l = r$.

Как проверить дерево за пять минут

Напишите тупое решение на массиве — цикл по отрезку — и сравните на случайных тестах:

for (int test = 0; test < 20000; test++) {
    int n = rnd(1, 8);
    // случайный массив, случайная последовательность операций
    // после каждой операции сверить ответы дерева и цикла
}

Ключевое здесь — маленькие $n$: на $n \le 8$ краевые случаи (отрезок из одного элемента, границы массива, совпавшие индексы) встречаются в каждом тесте, а на $n = 1000$ — почти никогда. Двадцать тысяч тестов по восемь элементов ловят больше, чем сто тестов по тысяче.

Подробнее про такую проверку — «Стресс-тестирование».

Отдельно про скорость

Если дерево верное, но не проходит по времени:

• рекурсия с std::function вместо обычной функции — замедление в разы;
• std::vector<std::vector<int>> в узлах вместо плоского массива;
• push там, где он не нужен (например, в задаче про площадь объединения);
• итеративное дерево вместо рекурсивного даёт ещё в полтора-два раза, если задача укладывается в его ограничения.