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

O(log n) per op

Дерево Фенвика хранит в каждой ячейке сумму небольшого блока, размер которого определяется младшим установленным битом ячейки. update() и query() оба прыгают по короткой цепочке таких блоков, поэтому оба работают за O(log n), даже пока данные продолжают меняться.

Сигналы

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

Шаблон

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

Похоже, но не то

Префиксные суммы: Префиксные суммы быстро отвечают на много запросов диапазона, но только после того, как массив построен и зафиксирован: одно обновление означает пересборку всего списка префиксов. Fenwick или дерево отрезков держат и точечные обновления, и запросы диапазона за O(log n) каждый, вперемешку и в реальном времени, чего префиксный массив не может.

n до 1e5..1e6 с чередующимися обновлениями и запросами диапазона -> O(log n) на обновление или запрос, каждый проходит короткую цепочку установленных битов.

Изучить этот паттерн