Подсчёт инверсий в массиве: наивно, сортировкой слиянием и деревом Фенвика

Как посчитать инверсии в массиве: перебор за O(n²), сортировка слиянием и дерево Фенвика за O(n log n). Разбор на примере, код на Python и задачи LeetCode 315 и 493.

13 мин чтенияалгоритмы · массивы · сортировка · python

Коротко

ПодходВремяПамятьКогда брать
Перебор всех парO(n2)O(n^2)O(1)O(1)nn до пары тысяч, проверка ответа
Сортировка слияниемO(nlog⁡n)O(n \log n)O(n)O(n)весь массив известен сразу
Дерево ФенвикаO(nlog⁡n)O(n \log n)O(n)O(n)элементы приходят потоком, нужны ответы по каждому
  • Инверсия — пара индексов i<ji < j, у которой ai>aja_i > a_j: больший элемент стоит раньше меньшего.
  • Число инверсий показывает, насколько массив «не отсортирован»: у отсортированного их 0, у развёрнутого — n(n−1)2\frac{n(n-1)}{2}.
  • Главная идея обоих быстрых способов одна: пары не перебираются, а считаются пачками.

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

Возьмём массив [5, 3, 8, 1, 2] и выпишем все пары, где левый элемент больше правого:

5 > 3   5 > 1   5 > 2
3 > 1   3 > 2
8 > 1   8 > 2

Семь инверсий. Пары 5, 8 и 1, 2 стоят в правильном порядке и не считаются.

Полезно держать в голове два факта:

  • Число инверсий равно минимальному числу обменов соседних элементов, которое нужно, чтобы отсортировать массив. Каждый такой обмен убирает ровно одну инверсию. Именно столько обменов сделает сортировка пузырьком.
  • Сортировка вставками работает за O(n+I)O(n + I), где II — число инверсий. Поэтому на почти отсортированных данных она быстрая, а на случайных — квадратичная.

Отсюда и максимум: в массиве, отсортированном по убыванию, каждая пара — инверсия, всего n(n−1)2\frac{n(n-1)}{2}. Для n=2⋅105n = 2 \cdot 10^5 это около 2⋅10102 \cdot 10^{10} — в 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

Это n(n−1)2\frac{n(n-1)}{2} сравнений, то есть O(n2)O(n^2). На Python массив из 5000 элементов считается около половины секунды, а на 10510^5 уже потребуются минуты.

На собеседовании это решение стоит назвать первым — одной фразой, с оценкой сложности, — и сразу перейти к оптимальному. А в коде оно пригодится как эталон для стресс-теста (об этом ниже).

Способ 1: сортировка слиянием

Интуиция

Разделим массив пополам. Любая инверсия попадает в одну из трёх групп:

  1. обе позиции в левой половине;
  2. обе позиции в правой половине;
  3. левый элемент в левой половине, правый — в правой.

Первые две группы посчитает рекурсия. Остаётся третья — межполовинные инверсии. Если обе половины уже отсортированы, их можно посчитать за один линейный проход. И этот проход — ровно шаг слияния из сортировки слиянием.

Где прячется счётчик

Сливаем отсортированные половины 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 (+)итого
540000
331011
852201
113034
224137

Снова 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.

Сложность

Сжатие — O(nlog⁡n)O(n \log n), затем nn раз по два действия за O(log⁡n)O(\log n). Итого O(nlog⁡n)O(n \log n) по времени и O(n)O(n) по памяти. Вместо Фенвика подойдёт и дерево отрезков — асимптотика та же, кода больше.

Какой способ выбрать

На 10510^5 случайных чисел в 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)

Нужно посчитать пары i<ji < j с условием ai>2⋅aja_i > 2 \cdot a_j. Это «усиленные» инверсии, и здесь слияние особенно удобно. Трюк — разделить подсчёт и слияние: пока обе половины отсортированы, двумя указателями считаем пары с новым условием, а потом сливаем как обычно.

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) — спрашивают, равно ли число всех инверсий числу соседних. Подсчёт за O(nlog⁡n)O(n \log n) проходит, но ожидают наблюдение: равенство верно тогда и только тогда, когда каждый элемент перестановки стоит не дальше чем на одну позицию от своего места.
  • Чётность перестановки. Перестановка чётная, если число инверсий чётное. На этом строится проверка разрешимости «пятнашек»: часть стартовых позиций в принципе не собирается.
  • Сравнение рейтингов. Расстояние Кендалла между двумя ранжированиями — это число инверсий в одном из них после перенумерации по другому. Так сравнивают, например, выдачу двух версий поиска.

Типичные ошибки

  1. Переполнение счётчика. Максимум — n(n−1)2\frac{n(n-1)}{2}. В Java/C++/Go используйте 64-битный тип. В JavaScript Number точно хранит целые до 2532^{53}, этого хватает.
  2. Строгое сравнение вместо нестрогого при слиянии. if a[i] < a[j] вместо <= засчитывает равные элементы как инверсии.
  3. Прибавить 1 вместо mid - i. Весь выигрыш алгоритма в том, что за один шаг засчитываются все оставшиеся элементы левой половины.
  4. Забыть сжатие координат перед Фенвиком. Дерево размера 10910^9 не поместится в память, а отрицательные индексы сломают цикл.
  5. Перепутать «не больше» и «строго меньше» в Фенвике: prefix(r) против prefix(r - 1). Первое нужно для подсчёта «больше» через вычитание, второе — для LeetCode 315.
  6. Испортить входной массив. Сортировка слиянием переставляет элементы. Если вызывающий код дальше работает с массивом, сделайте копию.

Как проверить себя

Перед сдачей быстрого решения стоит прогнать его против перебора на случайных маленьких массивах — с повторами и отрицательными числами:

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-задачи из этого семейства перестают пугать.

Потренироваться в спокойной обстановке

Все задачи