Где применяется
1. Задача
Дашборд мониторинга показывает пиковую задержку (самый медленный ответ) за любое окно, которое ты выберешь: последние 5 минут, последний час, всё утро. Новые замеры приходят постоянно и записываются поверх старых в буфер фиксированного размера (массив, длина которого не меняется). Нужен максимум на произвольном отрезке, и нужен быстро, пока данные меняются.
Дерево Фенвика из прошлого урока отвечало на запросы про отрезок при постоянных изменениях. Но оно опиралось на одно свойство: sum[l..r] можно получить как query(r) - query(l - 1). Всё держится на вычитании. Для максимума вычитания нет. Пример: максимум всего массива [2, 5, 1, 4] равен 5, максимум первых двух чисел тоже 5. По этим двум пятёркам нельзя узнать максимум последних двух чисел. Он может быть любым числом не больше 5. В этом массиве он равен 4.
Поэтому max, min и НОД (наибольший общий делитель) на меняющемся отрезке требуют другой структуры. Она хранит готовый ответ для каждого отрезка, а не восстанавливает его вычитанием.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- сумма или запрос на отрезке с точечными обновлениями вперемешку
- живой лидерборд или ранг, пока баллы меняются
- подсчёт инверсий или сколько более ранних значений больше
- запросы на отрезке, пока данные продолжают меняться
Похоже, но не то
- Префиксные суммы (Prefix sums)
Префиксные суммы читаются быстрее, но ломаются при любом изменении. Здесь платят log n за право менять.
- Массив разностей (Difference array)
Он принимает много изменений на отрезках и одно чтение в конце. Здесь чтения и записи перемешаны.
- Линия развёртки (подсчёт событий) (Sweep line (event counting))
Развёртка идёт по событиям в порядке сортировки и не оглядывается. Здесь запросы приходят в любом порядке.
- Бинарный поиск (массив) (Binary search (array))
Оба делят отрезок пополам на каждом шаге. Один ищет значение, другой сворачивает отрезок.
n до 1e6 и q смешанных операций дают O((n + q) log n). Память O(n) для дерева Фенвика.
На LeetCode
Задачи, где меняют отдельные значения и спрашивают максимум, минимум или другое объединение на отрезке, у которого нет вычитания. Дерево отрезков отвечает на оба запроса за O(log n) и ещё умеет спуститься к первой позиции, которая проходит проверку.
Класс из урока, где объединение это сложение, а нейтральное значение 0.
Построй максимум на отрезке по корзинам. Для каждого фрукта спустись к самой левой подходящей корзине и поставь в неё минус бесконечность.
Построй дерево по значениям. Для каждого числа v спроси максимум на значениях от v минус k до v минус 1, прибавь 1 и запиши в позицию v.