TLE на дереве отрезков с lazy: убрал рекурсию push — стало хуже. В чём дело?
Дерево отрезков с lazy (прибавление + сумма на отрезке) ловит TLE на 2·10^5 запросов. Пробовал убрать push из query, считая, что запрос данные не меняет — стало давать WA. Вернул push — снова TLE. Подскажите, где обычно константа течёт и что ускорить?
2 ответа
Сначала про WA: push в query убирать нельзя. Без него запрос вернёт устаревшие данные из детей, у которых висит непротолкнутая пометка. Так что push в query обязателен — это не источник TLE, это корректность.
Источники TLE на segment tree почти всегда такие:
- Медленный ввод-вывод. При 2·10^5 запросов
cin/coutбез ускорения легко даёт 2-3× замедление. Добавьте в началоmain:ios_base::sync_with_stdio(false); cin.tie(nullptr);. Это часто решает проблему целиком. - Рекурсия с передачей
(v, tl, tr, l, r)по значению — нормально, но глобальные массивыt[],lazy[]вместо полей структуры/вектора с проверками границ дают меньшую константу. long longвезде, где хватило бы int — для счётчиков индексов используйте int, long long только для сумм. Это влияет на кеш.- Лишние пересчёты — не вызывайте
t[v] = t[2v] + t[2v+1]там, где ничего не менялось.
Чаще всего виноват именно ввод-вывод. Сначала ускорьте его, потом профилируйте дальше.
Если ввод-вывод уже быстрый, а TLE держится — рассмотрите смену структуры. Для «прибавление на отрезке + сумма на отрезке» дерево отрезков с lazy избыточно: эта задача решается двумя деревьями Фенвика (трюк с разностями) за O(log n) на операцию, но с константой в разы меньше и без накладных расходов на рекурсию и push.
Ещё приём — итеративное lazy-дерево (bottom-up с проталкиванием по пути), оно быстрее рекурсивного по константе, но писать его аккуратно сложнее.
И проверьте асимптотику самого алгоритма: иногда TLE не в дереве, а в том, что вы делаете O(n) работы вокруг каждого запроса (например, заново читаете весь массив). Замерьте, сколько именно операций с деревом происходит — если их O(q log n) и q·log = 2·10^5 · 18 ≈ 3.6·10^6, то при быстром I/O это укладывается в лимит с огромным запасом, и проблема не в дереве.