Где применяется
1. Задача
Последний раздел курса собирает вместе многое из того, что ты уже построил. Дерево Фенвика и дерево отрезков соединяют массив, дерево и префиксные суммы. Они отвечают на вопросы про отрезок массива, когда данные всё время меняются.
Пример. Игровой рейтинг всю ночь получает очки игроков, по одному результату за раз. Игрок спрашивает: «Сколько человек сейчас набрали меньше меня?» Ответ нужен быстро, и он должен оставаться верным, пока приходят новые очки.
В уроке 24 были префиксные суммы. Один раз считаешь накопленные итоги, и потом любой вопрос «сумма первых i» решается одним чтением из массива, за O(1). Но стоит поменять одно значение, и все итоги после него становятся неверными. Массив итогов приходится пересчитывать, каждый раз за O(n).
Когда чтения и изменения идут вперемешку, а массив большой, пересчёт съедает всё время. Миллион изменений в массиве из миллиона чисел даёт миллион пересчётов по миллиону шагов. Нужна структура, где дёшево и изменить значение, и спросить сумму.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитarr = [2, 5, 1, 4, 3, 6]; query(1, 4); update(2, 3)Каждый узел хранит сумму своего отрезка, дерево построено один раз из [2, 5, 1, 4, 3, 6]. Ищем сумму arr[1..4].
Столбики: 40 значений, которые меняются с каждым изменением. У дерева Фенвика подсвеченный столбик означает ячейку дерева на этой позиции. Запросов n, изменений n / 4, и здесь, и в таблице ниже.
Одна операция: одно чтение или одна запись ячейки. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n·q)O(n + q log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- сумма или запрос на отрезке с точечными обновлениями вперемешку
- живой лидерборд или ранг, пока баллы меняются
- подсчёт инверсий или сколько более ранних значений больше
- запросы на отрезке, пока данные продолжают меняться
Похоже, но не то
- Префиксные суммы (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), а подсчёт идёт через прибавление 1 в позиции каждого значения.
Это класс из урока. Обновление прибавляет новое значение минус старое, а sumRange это rangeQuery со сдвигом позиций на 1.
Для каждого солдата посчитай меньшие и большие рейтинги с каждой стороны двумя деревьями по рейтингам. n не больше 1000, так что двойной цикл тоже проходит.
Иди справа, спроси, сколько меньших значений уже лежит в дереве, потом прибавь 1 в позиции текущего. Сдвинь значения на 10^4 + 1, чтобы позиции начинались с 1.
Сожми значения в ранги, иди справа и перед вставкой каждого числа посчитай уже сохранённые значения v, у которых 2v меньше него.