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

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

Дерево Фенвика хранит частичные суммы в массиве с индексами от 1. tree[i] покрывает блок, который кончается на i.

Длина блока равна младшему единичному биту i, это i & -i. Поэтому tree[4] покрывает позиции с 1 по 4, а tree[6] позиции 5 и 6.

query(i) прибавляет tree[i] и снимает с i младший бит. Цикл идёт, пока i не станет нулём, и возвращает сумму префикса.

update(i) прибавляет изменение к tree[i] и добавляет к i младший бит. Так изменение получает каждый блок, где лежит позиция i.

Оба цикла трогают около log n ячеек. Сумма отрезка это query(r) минус query(l - 1).

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

В дереве отрезков больше кода, чем в дереве Фенвика. Зато оно умеет минимум, максимум и отложенные изменения на отрезке.

Источники: Википедия: Дерево Фенвика, Википедия: Дерево отрезков, Fenwick (1994), A new data structure for cumulative frequency tables (англ.)

1. tree = [3, 4, 4, 9]Массив это [3, 1, 4, 1], индексы с 1. tree[4] покрывает все четыре.
2. query(3): tree[3] + tree[2]3 теряет младший бит и становится 2. Пока набрано 4 плюс 4.
3. query(3) = 82 теряет младший бит и становится 0. Сумма 8 это 3 + 1 + 4.
4. update(2, +5): tree[2] и tree[4]2 плюс младший бит даёт 4, а 8 уже за концом. Меняются две ячейки.
5. сумма с 2 по 3 = 13 - 3 = 10query(3) теперь 13, а query(1) равно 3. Разность и есть отрезок.

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;
    }
}

class Fenwick {
    private tree: number[];

    constructor(n: number) {
        this.tree = new Array<number>(n + 1).fill(0);
    }

    update(i: number, delta: number): void {
        for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
    }

    query(i: number): number {
        let sum = 0;
        for (; i > 0; i -= i & -i) sum += this.tree[i];
        return sum;
    }
}

class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

class Fenwick {
    private array $tree;
    public function __construct(int $n) { $this->tree = array_fill(0, $n + 1, 0); }
    public function update(int $i, int $delta): void {
        for (; $i < count($this->tree); $i += $i & -$i) $this->tree[$i] += $delta;
    }
    public function query(int $i): int {
        $sum = 0;
        for (; $i > 0; $i -= $i & -$i) $sum += $this->tree[$i];
        return $sum;
    }
}

    public static class Fenwick {
        private final int[] tree;

        public Fenwick(int n) {
            tree = new int[n + 1];
        }

        public void update(int i, int delta) {
            for (; i < tree.length; i += i & -i) tree[i] += delta;
        }

        public int query(int i) {
            int sum = 0;
            for (; i > 0; i -= i & -i) sum += tree[i];
            return sum;
        }
    }

    public class Fenwick {
        private readonly int[] tree;

        public Fenwick(int n) {
            tree = new int[n + 1];
        }

        public void Update(int i, int delta) {
            for (; i < tree.Length; i += i & -i) tree[i] += delta;
        }

        public int Query(int i) {
            int sum = 0;
            for (; i > 0; i -= i & -i) sum += 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;
}

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

Паттерн «Дерево Фенвика / дерево отрезков» нужен, когда в условии есть слова «сумма или запрос на отрезке с точечными обновлениями вперемешку», «живой лидерборд или ранг, пока баллы меняются» или «подсчёт инверсий или сколько более ранних значений больше». Решение на нём обычно укладывается в O(log n) per op.

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Дерево Фенвика / дерево отрезков» чаще всего путают с этими паттернами: Префиксные суммы, Массив разностей, Линия развёртки (подсчёт событий) и Бинарный поиск (массив).

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

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

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

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

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

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

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

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

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

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

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

Паттерн «Дерево Фенвика / дерево отрезков» решает такие задачи с собеседований: Сумма на отрезке с изменениями, Сколько меньших справа, Число сумм в диапазоне, Обратные пары, Минимум на отрезке, Сумма на прямоугольнике с изменениями и Мой календарь II.

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

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

У паттерна «Дерево Фенвика / дерево отрезков» целевая сложность O(log n) per op.

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