Частые баги в дереве отрезков: границы, индексация, переполнение в lazy — чек-лист?
Постоянно ловлю WA на деревьях отрезков и не могу быстро локализовать. Соберите, пожалуйста, чек-лист типовых граблей: границы отрезков, индексация, переполнение в lazy и т.п. — чтобы проверять по списку.
2 ответа
Чек-лист по убыванию частоты:
- Полуинтервал vs закрытый отрезок. Решите раз и навсегда:
[l, r]или[l, r). Смешение → ошибки на 1. Рекурсивные деревья обычно используют закрытый[tl, tr], итеративные — полуинтервал[l, r). - Нейтральный элемент. Сумма → 0, min →
LLONG_MAX, max →LLONG_MIN, gcd → 0, произведение → 1. Возврат при пустом пересечении (l > r) должен давать нейтраль, иначе испортите слияние. - Переполнение int. Сумма n значений до 10^9 переполняет int. В lazy
add * (tr - tl + 1)тем более. Держите суммы и пометки вlong long. Для произведений по модулю — приводите кlong longперед умножением. - Размер массива. Рекурсивное —
4*n; итеративное —2*n. Перепутали схему → выход за границы или порча данных. - push перед спуском. В lazy-дереве
pushобязателен и в update, и в query, до ухода в детей. - Пересборка t[v]. После рекурсии в update —
t[v] = combine(детей). Забыли → родитель неактуален.
Пройдитесь по списку — большинство WA отсюда.
Добавлю методику отладки, которая ловит баг за минуты:
Брутфорс-сверка. Напишите наивную O(n) реализацию (просто массив + цикл по [l, r]) и стресс-тест: генерируйте случайные малые n и случайные операции, прогоняйте обе реализации, сравнивайте ответы.
for (int test = 0; test < 100000; ++test) {
int n = rand() % 8 + 1;
// случайный массив, случайные update/query
// сравнить segtree.query(l,r) с brute(l,r)
// при расхождении — печатать сид и падать
}
На n ≤ 8 любой баг с границами/lazy вылезет за секунды, и у вас будет минимальный воспроизводящий тест. Это надёжнее, чем вглядываться в код.
Отдельно про lazy и присваивание 0: если пометка assign может быть нулём, нельзя кодировать «нет пометки» нулём — заведите отдельный флаг has_lazy. Это классический скрытый баг, который брутфорс ловит мгновенно.