0Pricing
Coding Interview Prep · Урок

Инверсии с BIT

Эффективно подсчитывайте пары не по порядку

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

Что такое инверсия

Инверсия — это пара i < j, для которой a[i] > a[j]. Это одна пара элементов, расположенных не по порядку; её подсчёт показывает, насколько массив неотсортирован.

Почему важны инверсии

Количество инверсий равно числу обменов, которые выполнила бы пузырьковая сортировка (sort). В задачах соревнований инверсии часто скрываются за вопросами о ранжировании и нарушении порядка.

Наивный подсчёт слишком медленный

Проверка каждой пары занимает O(n^2). При n около 100000 это десять миллиардов проверок — намного больше ограничения по времени. Нужен более эффективный подход. 🐢

Идея BIT

Просматривайте массив слева направо и спрашивайте: сколько элементов слева больше текущего? Дерево Фенвика отвечает на этот вопрос по мере прохода.

Подсчёт по частотам

BIT хранит таблицу частот значений. Операция обновления с параметрами (v, 1) фиксирует, что значение v уже встретилось в текущем проходе.

update(v, 1)

Большие значения образуют суффикс

Количество более ранних значений, больших чем v, равно числу уже встреченных значений минус числу значений до v включительно. Для i-го элемента это i минус запрос(v).

inv += i - query(v)

Сжатие координат

Если значения велики или отрицательны, сначала сопоставьте им ранги от 1 до n. Такое сжатие сохраняет BIT небольшим, не изменяя порядок значений.

rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}

Полный проход

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

for i, v in enumerate(a):
    inv += i - query(rank[v])
    update(rank[v], 1)

Работа за n log n

Для каждого элемента выполняются один запрос и одно обновление, каждое за O(log n). Весь подсчёт завершается за O(n log n). 🚀

Сортировка слиянием — родственный метод

Сортировка слиянием также считает инверсии за O(n log n) во время этапа слияния. Версия с BIT часто оказывается короче для написания в условиях ограниченного времени.

Следите за переполнением счётчика

Количество инверсий может достигать примерно n в квадрате, делённого на два, что очень много. Целые числа в Пайтоне не ограничены по размеру, но в других языках потребуется тип 64-разрядный.

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

Проверьте, насколько хорошо Вы понимаете стоимость прохода.

Повторение: подсчёт нарушений порядка

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

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

Урок «Инверсии с BIT» бесплатный?

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

Чему я научусь в уроке «Инверсии с BIT»?

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

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

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

Сколько времени занимает урок «Инверсии с BIT»?

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

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

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

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

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