Lazy propagation: прибавление на отрезке + сумма на отрезке — рабочая реализация?
Перешёл от точечных обновлений к обновлению на отрезке (прибавить delta ко всем a[l..r]) с запросом суммы. Понимаю, что нужна ленивая пометка, но всё время путаюсь, когда её применять и как проталкивать вниз. Дайте корректный шаблон с push.
2 ответа
Идея lazy propagation: когда обновление на отрезке полностью покрывает узел, мы не спускаемся в детей, а ставим узлу отложенную пометку lazy[v] и сразу чиним его t[v]. Реальное проталкивание в детей делаем лениво — только когда нужно зайти глубже.
long long t[4*N], lazy[4*N];
void apply(int v, int tl, int tr, long long add) {
t[v] += add * (tr - tl + 1); // сумма растёт на add * длину
lazy[v] += add;
}
void push(int v, int tl, int tr) {
if (lazy[v]) {
int tm = (tl + tr) / 2;
apply(2*v, tl, tm, lazy[v]);
apply(2*v+1, tm+1, tr, lazy[v]);
lazy[v] = 0;
}
}
void update(int v, int tl, int tr, int l, int r, long long add) {
if (l > r) return;
if (l == tl && r == tr) { apply(v, tl, tr, add); return; }
push(v, tl, tr);
int tm = (tl + tr) / 2;
update(2*v, tl, tm, l, min(r,tm), add);
update(2*v+1, tm+1, tr, max(l,tm+1), r, add);
t[v] = t[2*v] + t[2*v+1];
}
long long query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l == tl && r == tr) return t[v];
push(v, tl, tr);
int tm = (tl + tr) / 2;
return query(2*v, tl, tm, l, min(r,tm))
+ query(2*v+1, tm+1, tr, max(l,tm+1), r);
}
Золотое правило: push вызывается перед спуском в детей и в update, и в query. После рекурсии в update пересобираем t[v] из детей. Сложность: O(log n) на операцию, O(n) память.
Переполнение: add * (tr - tl + 1) легко выскакивает за int — держите всё в long long.
Самая частая ошибка новичков — забыть push в query. Запрос не меняет данные, кажется, что протолкнуть незачем. Но если у узла висит непротолкнутая пометка, а вы спускаетесь в его ребёнка, ребёнок вернёт устаревшую сумму → WA.
Вторая ошибка — обновлять t[v] после apply дважды. В apply сумма уже скорректирована; снаружи пересчёт t[v] нужен только когда вы спустились в детей (ветка с push), а не когда поставили пометку на весь узел.
И третье: для прибавления пометки накапливаются (lazy[v] += add), а нейтральная пометка — 0. Это отличает «add» от «assign», где пометка перезаписывается.