Дерево Фенвика / дерево отрезков

Дерево Фенвика / дерево отрезков: как это работает?

Каждый узел дерева владеет отрезком и хранит ответ по нему. Корню принадлежит весь массив.

Ответ узла собирается из двух его потомков. Правилом слияния служит сумма, минимум, максимум или похожее.

Запрос разбивает нужный отрезок по дереву. Он останавливается на узлах, целиком лежащих внутри.

Больше двух узлов на уровень никогда не нужно. Отсюда и log n работы на запрос.

Изменение правит один лист и поднимается к корню. Меняются только узлы над этим листом.

Дерево Фенвика делает то же для префиксных сумм гораздо меньшим кодом. Дерево отрезков умеет ещё минимум, максимум и отложенные изменения.

1. листья: 3, 1, 4, 1Массив это [3, 1, 4, 1]. Каждый лист владеет одной позицией.
2. уровень выше: 4 и 5Каждый узел суммирует двух своих потомков.
3. корень = 9В корне лежит сумма всего массива.
4. запрос с 1 по 2Нужный отрезок это 1 плюс 4. Его точно накрывают два узла.
5. запись 6 в индекс 1Меняются один лист и два узла над ним. Корень становится 14.

class Fenwick {
    constructor(n) { this.tree = new Array(n + 1).fill(0); }
    update(i, delta) {
        for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
    }
    query(i) {
        let sum = 0;
        for (; i > 0; i -= i & -i) sum += this.tree[i];
        return sum;
    }
}

Дерево Фенвика / дерево отрезков: разбор примера

Сколько меньших значений стоит справа

Для каждого элемента посчитайте, сколько более поздних элементов меньше него.

Вложенный цикл это O(n в квадрате), и он умирает на 1e5 элементов.

Идите по массиву справа налево, держа дерево Фенвика над значениями.

Для каждого элемента спросите, сколько меньших уже записано. Потом запишите текущий.

function countSmaller(nums) {
    const sorted = [...new Set(nums)].sort((a, b) => a - b);
    const rank = new Map(sorted.map((v, i) => [v, i + 1])); // ranks start at 1

    const tree = new Array(sorted.length + 1).fill(0);

    const add = (i) => {
        for (; i < tree.length; i += i & -i) tree[i]++;
    };

    const countBelow = (i) => {
        let total = 0;
        for (; i > 0; i -= i & -i) total += tree[i];
        return total;
    };

    const answer = new Array(nums.length);
    for (let i = nums.length - 1; i >= 0; i--) {
        const r = rank.get(nums[i]);
        answer[i] = countBelow(r - 1); // strictly smaller values already seen
        add(r);
    }

    return answer;
}

Дерево Фенвика / дерево отрезков: когда применять?

Эти формулировки в условии ведут сюда:

• •сумма или запрос на отрезке с точечными обновлениями вперемешку
• •живой лидерборд или ранг, пока баллы меняются
• •подсчёт инверсий или сколько более ранних значений больше
• •запросы на отрезке, пока данные продолжают меняться

Дерево Фенвика / дерево отрезков: с чем путают?

• Префиксные суммы (Prefix sums): Префиксные суммы читаются быстрее, но ломаются при любом изменении. Здесь платят log n за право менять.
• Массив разностей (Difference array): Он принимает много изменений на отрезках и одно чтение в конце. Здесь чтения и записи перемешаны.
• Линия развёртки (подсчёт событий) (Sweep line (event counting)): Развёртка идёт по событиям в порядке сортировки и не оглядывается. Здесь запросы приходят в любом порядке.
• Бинарный поиск (массив) (Binary search (array)): Оба делят отрезок пополам на каждом шаге. Один ищет значение, другой сворачивает отрезок.

Дерево Фенвика / дерево отрезков: частые ошибки

• Индексируют дерево Фенвика с нуля

  Шагу по младшему биту нужны индексы с единицы. Нулевой индекс зацикливает цикл.

• Берут его там, где ничего не меняется

  Префиксный массив отвечает за O(1) и ничего не стоит при чтении. Платите за дерево, только когда есть изменения.

• Забывают сжать значения

  Дерево размером с диапазон значений умирает на числах до 1e9. Сначала переведите их в ранги.

• Сливают отрезки неподходящим правилом

  Сумма и минимум работают, потому что порядок им не важен. Правилу, зависящему от порядка, нужно больше в узле.

Дерево Фенвика / дерево отрезков: задачи с собеседований

• Сумма на отрезке с изменениями: Чтения и записи идут вперемешку в любом порядке.
• Сколько меньших справа: Дерево Фенвика над сжатыми рангами.
• Число сумм в диапазоне: Префиксные суммы, поданные в дерево.
• Обратные пары: Подойдёт и сортировка слиянием, и дерево Фенвика.
• Минимум на отрезке: Дерево отрезков, поскольку у минимума нет обратной операции.
• Сумма на прямоугольнике с изменениями: Дерево, узлами которого служат другие деревья.
• Мой календарь II: Дерево отрезков с отложенными изменениями на отрезке.

Дерево Фенвика / дерево отрезков: сложность по времени и памяти

O(log n) per op

n до 1e6 и q смешанных операций дают O((n + q) log n). Память O(n) для дерева Фенвика.