Lazy propagation для присваивания на отрезке (assign) — чем отличается от прибавления?
С прибавлением на отрезке разобрался — там пометки складываются. А как сделать присвоить a[l..r] = x с запросом суммы? Пометки же не складываются, и непонятно, как отличить «нет пометки» от «присвоить 0».
2 ответа
У assign пометка не накапливается, а перезаписывает старую: последнее присваивание побеждает. Проблема ровно та, что вы назвали — значение 0 валидно, поэтому нельзя кодировать «нет пометки» нулём. Решение — флаг has_lazy[v].
long long t[4*N], lazy[4*N];
bool has[4*N];
void apply(int v, int tl, int tr, long long x) {
t[v] = x * (tr - tl + 1);
lazy[v] = x;
has[v] = true;
}
void push(int v, int tl, int tr) {
if (has[v]) {
int tm = (tl + tr) / 2;
apply(2*v, tl, tm, lazy[v]);
apply(2*v+1, tm+1, tr, lazy[v]);
has[v] = false;
}
}
update/query — как в обычном lazy-дереве (push перед спуском, пересборка t[v] = t[2v] + t[2v+1] после). Сложность O(log n) на операцию.
Ключ: apply для assign затирает и t, и пометку; для add — прибавляет. Поэтому нельзя слепо копировать шаблон add для assign.
Если в одной задаче нужны и assign, и add на отрезке одновременно — храните пару пометок и помните приоритет: assign «сильнее» add. При новом assign старый add обнуляется; при add поверх стоящего assign — add накапливается уже к присвоенному значению.
struct Lazy { bool assign=false; long long aval=0, add=0; };
// применяем к узлу:
// если приходит assign x: aval=x, assign=true, add=0
// если приходит add d: если assign активен -> aval+=d, иначе add+=d
Это и есть «комбинирование нескольких ленивых операций»: вы задаёте композицию пометок так, чтобы apply(apply(node, op1), op2) == apply(node, op2 ∘ op1). Самая частая граabля — перепутать порядок применения при проталкивании; всегда сначала assign родителя, потом его add.