0Pricing
Coding Interview Prep · Урок

Дерево Фенвика для префиксных сумм

Обновляйте точку и запрашивайте префикс за log n

«Дерево Фенвика для префиксных сумм» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Почему префиксные массивы не подходят

Обычный массив префиксных сумм мгновенно отвечает на запросы по диапазонам, но после одного обновления его приходится перестраивать. При большом количестве обновлений это становится медленным. ⏱️

Знакомьтесь: дерево Фенвика

Дерево Фенвика, или BIT, поддерживает точечные обновления и запросы префиксных сумм за O(log n). Это основной инструмент для динамических накопительных сумм.

Индексация с единицы по замыслу

Дерево Фенвика работает с массивом, индексация которого начинается с 1. Индекс 0 используется как пустой служебный элемент, поэтому все настоящие данные начинаются с позиции 1.

tree = [0] * (n + 1)

Магия младшего установленного бита

Каждый индекс охватывает блок значений. Размер блока равен i & -i — младшему установленному биту числа i. Этот простой приём лежит в основе всего дерева.

lowbit = i & -i

Обновление одной позиции

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

while i <= n:
    tree[i] += delta
    i += i & -i

Запрос префиксной суммы

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

s = 0
while i > 0:
    s += tree[i]
    i -= i & -i

Оба цикла логарифмические

Каждый цикл на одной итерации сбрасывает один бит, поэтому выполняется не более log n раз. Именно поэтому и обновление, и запрос остаются быстрыми.

Сумма на диапазоне из двух префиксов

Нужна сумма от l до r? Возьмите префикс(r) минус префикс(l-1), как в статическом префиксном массиве, но теперь обновления тоже выполняются быстро.

range_sum = query(r) - query(l - 1)

Построение дерева

При самом простом построении для каждого исходного значения вызывается обновление. Это занимает O(n log n) и достаточно быстро для большинства соревнований.

for i, v in enumerate(a, 1):
    update(i, v)

Минимальный объём памяти

Дереву Фенвика нужен всего один массив размера n+1. Такой компактный объём памяти — одна из причин его популярности на соревнованиях. 💾

Когда выбирать BIT

Выбирайте дерево Фенвика, когда чередуются точечные обновления и запросы префиксных сумм или сумм на диапазонах. Его код краток, а превзойти его по удобству трудно.

Быстрая проверка

Закрепим, как перемещаются циклы.

Повторение: основы BIT

Вы познакомились с деревом Фенвика: оно использует индексацию с единицы и выражение i & -i, а точечное обновление и запрос префиксной суммы выполняются за O(log n). Далее мы используем его для подсчёта инверсий. 🎯

Часто задаваемые вопросы

Урок «Дерево Фенвика для префиксных сумм» бесплатный?

Да — полный текст урока «Дерево Фенвика для префиксных сумм» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Дерево Фенвика для префиксных сумм»?

Обновляйте точку и запрашивайте префикс за log n Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Дерево Фенвика для префиксных сумм»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Дерево Фенвика для префиксных сумм
  2. Инверсии с BIT
  3. Дерево отрезков: построение и запросы
  4. Отложенное распространение для обновлений диапазонов
← Назад к Coding Interview Prep