Дерево Фенвика (BIT)

Суммы префиксов И точечные обновления — оба за O(log n).

время O(log n)память O(n)уровень: средний

Что происходит сейчас0/0

Нажмите Play, чтобы запустить сценарий

TypeScript — активная строка подсвечена шагом

1class FenwickTree {
2  private t: number[] // t[i] хранит сумму диапазона (i - lowbit(i), i]
3 
4  constructor(n: number) {
5    this.t = new Array(n + 1).fill(0)
6  }
7 
8  add(i: number, delta: number): void {
9    for (; i < this.t.length; i += i & -i) this.t[i]! += delta
10  }
11 
12  prefixSum(i: number): number {
13    let s = 0
14    for (; i > 0; i -= i & -i) s += this.t[i]!
15    return s
16  }
17}

Проблема

Суммы префиксов И точечные обновления — оба за O(log n).

Что вы видите

t[i] накрывает диапазон длиной в свой младший бит; прыжки i±=(i&-i).

Как это работает

Гениальная упаковка дерева в массив: без указателей, 5 строк кода. Обновление и сумма — зеркальные циклы по битам индекса.

Пошаговый разбор

01
Структура
t[i] = сумма своего диапазона.
02
Сумма
Прыжки вниз по битам.
03
Обновление
Прыжки вверх.

Complexity и ограничения

time

O(log n)

space

O(n)

Сложность см. в шапке страницы.

Edge cases

Пустой вход
Корректная тривиальная обработка.
Вырожденный случай
Минимум работы — сразу ответ.

Где встречается в реальности

Рейтинги

Динамика позиций.

Счётчики

Просмотры за период.

Соревнования

Баллы в реальном времени.

Связанные алгоритмы

Префиксные суммы Дерево отрезков

Shorts

«Дерево в массиве без указателей»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Дерево в массиве без указателей

Нажмите Play

Бит 1/6 · 0–2 с

Hook

script-setup.ru/algorithms/fenwick