Подсчёт инверсий в массиве: наивно, сортировкой слиянием и деревом Фенвика
Как посчитать инверсии в массиве: перебор за O(n²), сортировка слиянием и дерево Фенвика за O(n log n). Разбор на примере, код на Python и задачи LeetCode 315 и 493.
Коротко
| Подход | Время | Память | Когда брать |
|---|---|---|---|
| Перебор всех пар | до пары тысяч, проверка ответа | ||
| Сортировка слиянием | весь массив известен сразу | ||
| Дерево Фенвика | элементы приходят потоком, нужны ответы по каждому |
- Инверсия — пара индексов , у которой : больший элемент стоит раньше меньшего.
- Число инверсий показывает, насколько массив «не отсортирован»: у отсортированного их 0, у развёрнутого — .
- Главная идея обоих быстрых способов одна: пары не перебираются, а считаются пачками.
Что такое инверсия
Возьмём массив [5, 3, 8, 1, 2] и выпишем все пары, где левый элемент больше правого:
5 > 3 5 > 1 5 > 2
3 > 1 3 > 2
8 > 1 8 > 2
Семь инверсий. Пары 5, 8 и 1, 2 стоят в правильном порядке и не считаются.
Полезно держать в голове два факта:
- Число инверсий равно минимальному числу обменов соседних элементов, которое нужно, чтобы отсортировать массив. Каждый такой обмен убирает ровно одну инверсию. Именно столько обменов сделает сортировка пузырьком.
- Сортировка вставками работает за , где — число инверсий. Поэтому на почти отсортированных данных она быстрая, а на случайных — квадратичная.
Отсюда и максимум: в массиве, отсортированном по убыванию, каждая пара — инверсия, всего . Для это около — в 32-битный int не влезет. В Java и C++ счётчик сразу объявляйте как long.
Наивное решение: перебор пар
Самое прямое — проверить все пары:
def count_inversions_naive(a): n = len(a) count = 0 for i in range(n): for j in range(i + 1, n): if a[i] > a[j]: count += 1 return count print(count_inversions_naive([5, 3, 8, 1, 2])) # 7
Это сравнений, то есть . На Python массив из 5000 элементов считается около половины секунды, а на уже потребуются минуты.
На собеседовании это решение стоит назвать первым — одной фразой, с оценкой сложности, — и сразу перейти к оптимальному. А в коде оно пригодится как эталон для стресс-теста (об этом ниже).
Способ 1: сортировка слиянием
Интуиция
Разделим массив пополам. Любая инверсия попадает в одну из трёх групп:
- обе позиции в левой половине;
- обе позиции в правой половине;
- левый элемент в левой половине, правый — в правой.
Первые две группы посчитает рекурсия. Остаётся третья — межполовинные инверсии. Если обе половины уже отсортированы, их можно посчитать за один линейный проход. И этот проход — ровно шаг слияния из сортировки слиянием.
Где прячется счётчик
Сливаем отсортированные половины L и R двумя указателями i и j. Пусть на очередном шаге R[j] < L[i]. Тогда R[j] меньше не только L[i], но и всех элементов L правее него: левая половина отсортирована. Значит, R[j] образует инверсию с каждым из оставшихся len(L) - i элементов — и мы прибавляем их все разом.
Если же L[i] <= R[j], инверсии нет, просто забираем элемент слева.
Код
def count_inversions_merge(a): def sort(lo, hi):
# сортирует a[lo:hi] и возвращает число инверсий внутри
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
count = sort(lo, mid) + sort(mid, hi)
merged = []
i, j = lo, mid
while i < mid and j < hi:
if a[i] <= a[j]:
merged.append(a[i])
i += 1
else:
# a[j] меньше всех оставшихся слева: a[i..mid-1]
count += mid - i
merged.append(a[j])
j += 1
merged.extend(a[i:mid])
merged.extend(a[j:hi])
a[lo:hi] = merged
return count
a = list(a) # не портим входной массив
return sort(0, len(a))
print(count_inversions_merge([5, 3, 8, 1, 2])) # 7
Обратите внимание на `<=` в сравнении. Равные элементы инверсию не образуют, поэтому при равенстве забираем левый элемент, ничего не прибавляя. Если написать `<`, пары одинаковых чисел посчитаются как инверсии, и ответ на `[1, 1]` станет 1 вместо 0.
### Разбор на примере
Массив `[5, 3, 8, 1, 2]`, делим по `mid = 2`:
[5, 3] | [8, 1, 2] [5] [3] | [8] [1, 2] | [1] [2] → 0 слияние: 3 < 5 → +1 слияние [8] и [1, 2]: → [3, 5], всего 1 1 < 8 → +1, 2 < 8 → +1 → [1, 2, 8], всего 2
Финальное слияние `[3, 5]` и `[1, 2, 8]`:
| Шаг | L[i] | R[j] | Действие | Прибавили |
| --- | ---- | ---- | ------------------- | ------------- |
| 1 | 3 | 1 | 1 < 3, берём справа | 2 (это 3 и 5) |
| 2 | 3 | 2 | 2 < 3, берём справа | 2 |
| 3 | 3 | 8 | 3 ≤ 8, берём слева | 0 |
| 4 | 5 | 8 | 5 ≤ 8, берём слева | 0 |
Межполовинных инверсий 4, итого $1 + 2 + 4 = 7$. Совпадает с перебором.
### Сложность
Это обычная сортировка слиянием, к которой добавили одно сложение на шаг. Рекуррента $T(n) = 2T(n/2) + O(n)$, ответ — $O(n \log n)$ по времени и $O(n)$ по памяти. Глубина рекурсии $\log_2 n$ — для $10^5$ элементов около 17, так что лимит рекурсии в Python не мешает.
Побочный эффект — массив сортируется. Если исходный порядок ещё нужен, работайте с копией, как в коде выше.
## Способ 2: дерево Фенвика
### Идея
Пойдём по массиву слева направо. Для каждого элемента `x` спросим: **сколько из уже пройденных элементов больше `x`?** Каждый такой элемент стоит левее и больше — это инверсия. Сумма ответов по всем `x` — искомое число.
Нужна структура, которая умеет две операции:
- отметить, что значение `x` встретилось;
- быстро сказать, сколько отмеченных значений не больше `x`.
Если завести массив счётчиков `cnt[v]` — сколько раз встретилось значение `v`, — то второй запрос превращается в префиксную сумму `cnt[1] + ... + cnt[x]`. Префиксная сумма с точечными обновлениями — ровно то, что делает [дерево Фенвика](/blog/fenwick-tree): обе операции за $O(\log n)$.
Тогда «больше `x`» = «уже прошли» минус «не больше `x`».
### Сжатие координат
Значения могут быть огромными (до $10^9$) или отрицательными, а дерево Фенвика индексируется числами от 1 до $m$. Важен только относительный порядок элементов, поэтому заменим каждое значение его рангом среди уникальных: наименьшее → 1, следующее → 2 и так далее. Это сжатие координат, оно стоит $O(n \log n)$ на сортировку.
### Код
```python
class Fenwick:
def __init__(self, n):
self.tree = [0] * (n + 1)
def add(self, i, delta=1):
while i < len(self.tree):
self.tree[i] += delta
i += i & -i
def prefix(self, i):
# сумма на позициях 1..i
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def count_inversions_fenwick(a):
values = sorted(set(a))
rank = {v: i + 1 for i, v in enumerate(values)} # 1-индексация
bit = Fenwick(len(values))
count = 0
for seen, x in enumerate(a):
r = rank[x]
# seen элементов уже добавлено, из них prefix(r) не больше x
count += seen - bit.prefix(r)
bit.add(r)
return count
print(count_inversions_fenwick([5, 3, 8, 1, 2])) # 7
Равные элементы обрабатываются автоматически: prefix(r) включает сам ранг r, поэтому одинаковые значения попадают в «не больше» и инверсией не считаются.
Разбор на примере
Для [5, 3, 8, 1, 2] ранги такие: 1 → 1, 2 → 2, 3 → 3, 5 → 4, 8 → 5.
| x | ранг | уже прошли | не больше x | больше x (+) | итого |
|---|---|---|---|---|---|
| 5 | 4 | 0 | 0 | 0 | 0 |
| 3 | 3 | 1 | 0 | 1 | 1 |
| 8 | 5 | 2 | 2 | 0 | 1 |
| 1 | 1 | 3 | 0 | 3 | 4 |
| 2 | 2 | 4 | 1 | 3 | 7 |
Снова 7.
То же на JavaScript
function countInversions(a) { const values = [...new Set(a)].sort((x, y) => x - y) const rank = new Map(values.map((v, i) => [v, i + 1])) const tree = new Array(values.length + 1).fill(0) let count = 0 for (let seen = 0; seen < a.length; seen++) { const r = rank.get(a[seen]) // сколько уже добавленных элементов не больше a[seen] let notGreater = 0 for (let i = r; i > 0; i -= i & -i) notGreater += tree[i] count += seen - notGreater for (let i = r; i < tree.length; i += i & -i) tree[i] += 1 } return count } console.log(countInversions([5, 3, 8, 1, 2])) // 7 console.log(countInversions([10, -1, 100, -50])) // 4
Компаратор (x, y) => x - y обязателен: без него sort() сравнивает числа как строки, и -50 окажется после -1, а 100 — перед 10.
Сложность
Сжатие — , затем раз по два действия за . Итого по времени и по памяти. Вместо Фенвика подойдёт и дерево отрезков — асимптотика та же, кода больше.
Какой способ выбрать
На случайных чисел в CPython оба варианта укладываются в доли секунды: слияние около 0,2 с, Фенвик около 0,3 с. Разница не в скорости, а в том, что каждый умеет.
| Сортировка слиянием | Дерево Фенвика | |
|---|---|---|
| Нужны ли все данные сразу | да | нет, можно онлайн |
| Ответ для каждого элемента | можно, но сложнее (через индексы) | естественно |
| Портит массив | сортирует (работаем с копией) | нет |
| Нужно сжатие координат | нет | да, если значения большие |
Обобщается на условие a[i] > 2·a[j] | легко | нужен поиск ранга 2·a[j] |
Правило: если нужно одно число для всего массива — слияние, оно короче и не требует дополнительных структур. Если элементы приходят по одному или нужен ответ по каждой позиции — Фенвик.
Где это встречается на собеседованиях
Голая задача «посчитай инверсии» на LeetCode отдельно не выделена, но её идея лежит в основе нескольких популярных Hard-задач.
Count of Smaller Numbers After Self (LeetCode 315)
Для каждого nums[i] нужно вернуть, сколько элементов правее него строго меньше. Это инверсии, разложенные по левому концу: сумма ответа равна общему числу инверсий.
Решение через Фенвика: идём справа налево, для каждого элемента спрашиваем количество уже добавленных строго меньших (prefix(r - 1)), потом добавляем себя.
from bisect import bisect_left def count_smaller(nums): values = sorted(set(nums)) bit = Fenwick(len(values)) # класс из раздела выше result = [0] * len(nums) for i in range(len(nums) - 1, -1, -1): r = bisect_left(values, nums[i]) + 1 result[i] = bit.prefix(r - 1) # строго меньше bit.add(r) return result print(count_smaller([5, 2, 6, 1])) # [2, 1, 1, 0]
Через слияние тоже можно, но сортировать придётся индексы, а не значения: иначе после перестановок не понять, к какому элементу прибавлять. Когда элемент из левой половины уходит в результат, правее него и меньше него ровно столько элементов, сколько уже забрано из правой половины, то есть j - mid:
def count_smaller_merge(nums): n = len(nums) result = [0] * n idx = list(range(n)) # сортируем индексы, а не значения def sort(lo, hi): if hi - lo <= 1: return mid = (lo + hi) // 2 sort(lo, mid) sort(mid, hi) merged = [] i, j = lo, mid while i < mid and j < hi: if nums[idx[j]] < nums[idx[i]]: merged.append(idx[j]) j += 1 else: # правее idx[i] и меньше него ровно j - mid элементов result[idx[i]] += j - mid merged.append(idx[i]) i += 1 while i < mid: result[idx[i]] += j - mid merged.append(idx[i]) i += 1 merged.extend(idx[j:hi]) idx[lo:hi] = merged sort(0, n) return result print(count_smaller_merge([5, 2, 6, 1])) # [2, 1, 1, 0]
Здесь счётчик прибавляется не тогда, когда берём элемент справа, а когда забираем левый: так ответ привязан к конкретному индексу. Частая ошибка — забыть хвост while i < mid: оставшимся левым элементам тоже нужно прибавить j - mid.
Reverse Pairs (LeetCode 493)
Нужно посчитать пары с условием . Это «усиленные» инверсии, и здесь слияние особенно удобно. Трюк — разделить подсчёт и слияние: пока обе половины отсортированы, двумя указателями считаем пары с новым условием, а потом сливаем как обычно.
def reverse_pairs(nums): def sort(lo, hi): if hi - lo <= 1: return 0 mid = (lo + hi) // 2 count = sort(lo, mid) + sort(mid, hi) # 1. считаем пары: обе половины уже отсортированы j = mid for i in range(lo, mid): while j < hi and nums[i] > 2 * nums[j]: j += 1 count += j - mid # 2. обычное слияние nums[lo:hi] = sorted(nums[lo:hi]) return count nums = list(nums) return sort(0, len(nums)) print(reverse_pairs([1, 3, 2, 3, 1])) # 2 print(reverse_pairs([2, 4, 3, 5, 1])) # 3
Указатель j только растёт: если nums[i] > 2 * nums[j], то и следующий, больший nums[i] тоже больше. Поэтому подсчёт линейный.
Для слияния здесь использован sorted. Это не жульничество со сложностью: Timsort находит в срезе две готовые отсортированные серии и сливает их за линейное время. На собеседовании, впрочем, лучше написать слияние руками или хотя бы проговорить этот довод.
Попытка совместить подсчёт и слияние в одном цикле — классическая ошибка. Условие слияния (<) и условие подсчёта (> 2·) разные, и один указатель не может обслуживать оба.
Другие места
- Минимум соседних обменов для сортировки массива или перестановки строки в другую — ответ равен числу инверсий. Встречается в задачах вида «за сколько обменов соседних можно получить...».
- Global and Local Inversions (LeetCode 775) — спрашивают, равно ли число всех инверсий числу соседних. Подсчёт за проходит, но ожидают наблюдение: равенство верно тогда и только тогда, когда каждый элемент перестановки стоит не дальше чем на одну позицию от своего места.
- Чётность перестановки. Перестановка чётная, если число инверсий чётное. На этом строится проверка разрешимости «пятнашек»: часть стартовых позиций в принципе не собирается.
- Сравнение рейтингов. Расстояние Кендалла между двумя ранжированиями — это число инверсий в одном из них после перенумерации по другому. Так сравнивают, например, выдачу двух версий поиска.
Типичные ошибки
- Переполнение счётчика. Максимум — . В Java/C++/Go используйте 64-битный тип. В JavaScript
Numberточно хранит целые до , этого хватает. - Строгое сравнение вместо нестрогого при слиянии.
if a[i] < a[j]вместо<=засчитывает равные элементы как инверсии. - Прибавить 1 вместо
mid - i. Весь выигрыш алгоритма в том, что за один шаг засчитываются все оставшиеся элементы левой половины. - Забыть сжатие координат перед Фенвиком. Дерево размера не поместится в память, а отрицательные индексы сломают цикл.
- Перепутать «не больше» и «строго меньше» в Фенвике:
prefix(r)противprefix(r - 1). Первое нужно для подсчёта «больше» через вычитание, второе — для LeetCode 315. - Испортить входной массив. Сортировка слиянием переставляет элементы. Если вызывающий код дальше работает с массивом, сделайте копию.
Как проверить себя
Перед сдачей быстрого решения стоит прогнать его против перебора на случайных маленьких массивах — с повторами и отрицательными числами:
import random for _ in range(1000): a = [random.randint(-5, 5) for _ in range(random.randint(0, 20))] expected = count_inversions_naive(a) assert count_inversions_merge(a) == expected, a assert count_inversions_fenwick(a) == expected, a print("ok")
Маленький диапазон значений здесь не случаен: так почти в каждом тесте будут одинаковые элементы, на которых ломается большинство реализаций.
Итог
Подсчёт инверсий — короткая задача, которая проверяет сразу две вещи: умеете ли вы встроить подсчёт в «разделяй и властвуй» и умеете ли превратить вопрос «сколько элементов больше» в префиксную сумму. Обе идеи переносятся на LeetCode 315 и 493 почти без изменений. Если готовитесь к собеседованию, напишите оба способа с нуля и прогоните стресс-тест — после этого Hard-задачи из этого семейства перестают пугать.