Дерево отрезков на максимум с восстановлением позиции максимума?
Нужно не просто найти максимум на отрезке, но и индекс, где он достигается (если максимумов несколько — любой, или, скажем, самый левый). Как хранить и сливать так, чтобы позиция тоже корректно поднималась наверх?
2 ответа
Храните в узле пару (значение, индекс). При слиянии берёте пару с большим значением; при равенстве — ту, у которой меньше индекс (чтобы получить самый левый максимум).
struct Node { long long val; int idx; };
Node t[4 * 100000];
long long a[100000];
Node merge(const Node& x, const Node& y) {
if (x.val > y.val) return x;
if (y.val > x.val) return y;
return (x.idx <= y.idx) ? x : y; // равны -> левый
}
void build(int v, int tl, int tr) {
if (tl == tr) { t[v] = {a[tl], tl}; return; }
int tm = (tl + tr) / 2;
build(2*v, tl, tm); build(2*v+1, tm+1, tr);
t[v] = merge(t[2*v], t[2*v+1]);
}
Node query(int v, int tl, int tr, int l, int r) {
if (l == tl && r == tr) return t[v];
int tm = (tl + tr) / 2;
if (r <= tm) return query(2*v, tl, tm, l, r);
if (l > tm) return query(2*v+1, tm+1, tr, l, r);
return merge(query(2*v, tl, tm, l, tm),
query(2*v+1, tm+1, tr, tm+1, r));
}
Обновление точки — как обычно, в листе пишем {val, pos} и пересобираем предков через merge. Сложность build O(n), update/query O(log n), память O(n).
Заметьте: я разбил query на три ветки (целиком слева / целиком справа / пересекает), чтобы не возиться с нейтральным элементом для структуры. Так чище для пары значение-индекс.
Альтернатива без хранения индекса в узле: держите обычное дерево на максимум, найдите значение M = max на [l,r], а затем спуститесь по дереву за O(log n), ища первую (самую левую) позицию со значением M. Это полезно, когда индекс нужен редко — экономите память и упрощаете merge.
// найти самую левую позицию p в [l,r], где a[p] == target
int descend(int v, int tl, int tr, int l, int r, long long target) {
if (t[v] < target || r < tl || tr < l) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int res = descend(2*v, tl, tm, l, r, target);
if (res != -1) return res;
return descend(2*v+1, tm+1, tr, l, r, target);
}
Это тоже O(log n) за счёт отсечения поддеревьев, где максимум меньше target.