Дерево ФенвикаFenwick Tree

Идея дерева Фенвика: индекс i в массиве bit хранит не значение a[i], а сумму диапазона, длина которого равна lowbit(i) = i & (-i) — младшему установленному биту числа i в двоичной записи, — заканчивающегося на позиции i. Например, bit[6] (110₂, lowbit=2) хранит сумму a[5..6]; bit[8] (1000₂, lowbit=8) хранит сумму a[1..8]. Эта на первый взгляд странная схема даёт удивительно простую арифметику для обоих направлений движения по дереву, полностью через побитовые операции, без единого указателя.The Fenwick tree's idea: index i in the bit array doesn't store the value a[i], but the sum of a range whose length equals lowbit(i) = i & (-i) — the lowest set bit of i's binary representation — ending at position i. For example, bit[6] (110₂, lowbit=2) stores the sum a[5..6]; bit[8] (1000₂, lowbit=8) stores the sum a[1..8]. This seemingly odd scheme gives surprisingly simple arithmetic for movement in both directions through the tree, entirely via bitwise operations, with not a single pointer.

Запрос префиксной суммы prefix(i) = a[1]+...+a[i] идёт "вниз" по убывающим индексам: взять bit[i], затем перейти к i - lowbit(i) и повторить, пока i не станет 0 — каждый шаг убирает младший установленный бит числа i, поэтому шагов не больше, чем битов в i, то есть O(log n). Точечное обновление update(i, delta) идёт "вверх" по возрастающим индексам: прибавить delta к bit[i], затем перейти к i + lowbit(i) и повторить, пока i не превысит n — симметричная операция, тоже O(log n) шагов. Сумма произвольного диапазона [l, r] получается как prefix(r) - prefix(l-1) — именно эта финальная операция и требует обратимости: без вычитания эта формула невозможна.A prefix-sum query prefix(i) = a[1]+...+a[i] moves "down" through decreasing indices: take bit[i], then move to i - lowbit(i) and repeat until i reaches 0 — each step removes i's lowest set bit, so there are no more steps than bits in i, i.e. O(log n). A point update, update(i, delta), moves "up" through increasing indices: add delta to bit[i], then move to i + lowbit(i) and repeat until i exceeds n — the symmetric operation, also O(log n) steps. A range sum [l, r] is obtained as prefix(r) - prefix(l-1) — it's precisely this final operation that requires invertibility: without subtraction, this formula is impossible.

struct Fenwick {
    std::vector<long long> bit;      // 1-индексированный, размер n+1// 1-indexed, size n+1
    int n;
    Fenwick(int n_) : n(n_), bit(n_ + 1, 0) {}

    void update(int i, long long delta) {     // a[i] += delta, i — 1-индексирован// a[i] += delta, i is 1-indexed
        for (; i <= n; i += i & (-i))
            bit[i] += delta;
    }

    long long prefix(int i) const {         // сумма a[1..i]// sum of a[1..i]
        long long s = 0;
        for (; i > 0; i -= i & (-i))
            s += bit[i];
        return s;
    }

    long long range_sum(int l, int r) const {   // сумма a[l..r], 1-индексировано, включительно// sum of a[l..r], 1-indexed, inclusive
        return prefix(r) - prefix(l - 1);        // требует обратимости операции!// requires the operation to be invertible!
    }
};

Массив bit нарисован как плоский ряд ячеек — никакой отдельной древовидной картинки, потому что дерева как структуры данных здесь буквально нет. prefix(i) проигрывает шаги i -= lowbit(i) с подсветкой посещённых ячеек; update(i, delta) — шаги i += lowbit(i).The bit array is drawn as a flat row of cells — no separate tree diagram, because there literally is no tree as a data structure here. prefix(i) auto-plays the i -= lowbit(i) steps, highlighting visited cells; update(i, delta) plays the i += lowbit(i) steps.

range_sum(l, r) = prefix(r) - prefix(l-1) полагается на существование обратной операции: сложение обратимо вычитанием, XOR обратим самим собой (a ⊕ b ⊕ b = a). Минимум и максимум необратимы: если prefix_min(r) = 2 и prefix_min(l-1) = 2, невозможно определить, был ли этот минимум 2 внутри диапазона [l, r] или пришёл из префикса [1, l-1] — операция min "забывает" информацию, необходимую для его же обращения. Для запросов min/max по диапазону нужна либо структура, которая явно хранит достаточно информации для восстановления (segment tree — 2.3.2.6, где каждый узел хранит агрегат именно своего диапазона, а не только префикса), либо sparse table для статичных данных (диапазонный минимум с O(1) на запрос после O(n log n) препроцессинга, но без поддержки обновлений).range_sum(l, r) = prefix(r) - prefix(l-1) relies on an inverse operation existing: addition is inverted by subtraction, XOR is its own inverse (a ⊕ b ⊕ b = a). Min and max are not invertible: if prefix_min(r) = 2 and prefix_min(l-1) = 2, there's no way to tell whether that minimum of 2 came from inside the range [l, r] or from the prefix [1, l-1] — the min operation "forgets" the information needed to invert itself. Range min/max queries need either a structure that explicitly stores enough information to recover the answer (a segment tree — 2.3.2.6, where every node stores the aggregate of exactly its own range, not just a prefix), or a sparse table for static data (range minimum with O(1) per query after O(n log n) preprocessing, but no update support).