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