Что ещё делают этим приёмом

Если ты знаешь ещё три-четыре задачи, решаемые делением с разбором границы, и понимаешь, почему в многомерии схема ломается, листай до «Теперь сам».

Как думаешь, что общего у этих задач

Посмотри на четыре задачи: найти ближайшую пару точек; посчитать, сколько пар элементов массива стоят в неправильном порядке; построить выпуклую оболочку множества точек; нарисовать силуэт города из прямоугольных домов.

Геометрия, комбинаторика, графика - разные области. Но решаются все четыре одинаково, и не потому, что кто-то так захотел: у них одинаковое устройство ответа.

На что это похоже

Разбор архива по годам. Хочешь посчитать, сколько документов ссылаются друг на друга: раздели архив на две половины, посчитай внутри каждой, а потом отдельно разберись со ссылками «из первой половины во вторую». Если эти межполовинные ссылки удаётся посчитать не перебором, а одним проходом, - схема работает, какой бы ни была предметная область.

Механизм: четыре задачи одним приёмом

ЧИСЛО ИНВЕРСИЙ (пар i < j, где a[i] > a[j])
    делим пополам, считаем внутри каждой половины
    граница: при слиянии, забирая элемент из правой половины,
             прибавляем число оставшихся слева - это инверсии через разрез
    T(n) = 2·T(n/2) + n → Θ(n·log n)

ВЫПУКЛАЯ ОБОЛОЧКА
    делим точки по x, строим оболочку каждой половины
    граница: найти две «мостовые» касательные между оболочками за O(n)
    T(n) = 2·T(n/2) + n → Θ(n·log n)

СИЛУЭТ ГОРОДА (skyline)
    делим список домов пополам, строим силуэт каждой половины
    граница: слить два силуэта, идя слева направо и беря максимум высоты
    T(n) = 2·T(n/2) + n → Θ(n·log n)

БЛИЖАЙШАЯ ПАРА
    граница: полоса шириной 2d, семь соседей по y

Общий признак: ответ либо целиком внутри половины, либо задевает границу, и пограничные случаи описываются узкой зоной или одним линейным проходом.

КОГДА СХЕМА ЛОМАЕТСЯ

многомерие      в k измерениях ограничить удаётся не все оси, и константа «семь»
                не получается вовсе: сетка вместо деления, 3^k клеток на точку
перекрытие      подзадачи запрашивают одно и то же - это уже не деление пополам,
                а динамическое программирование (раздел 15): ответы подзадач
                запоминают, чтобы не считать дважды
дорогая граница объединение стоит n² - выигрыш исчезает целиком

Правило

Приём применим, когда ответ распадается на «внутри левой», «внутри правой» и «через границу», а пограничный случай считается за линию или почти за линию. Так решаются ближайшая пара, число инверсий, выпуклая оболочка, силуэт города, подсчёт пересечений. В пространстве большой размерности схема вырождается: аналог полосы содержит слишком много точек, и вместо деления берут сетку, kd-дерево или хеширование, чувствительное к близости. Для ближайшей пары существует и рандомизированный алгоритм с ожидаемым временем O(n) - он строит сетку с шагом текущего минимума и перестраивает её по мере уточнения.

Разбор: число инверсий - та же схема без геометрии

Массив [5, 2, 8, 1]. Инверсия - пара i < j, где a[i] > a[j].

делим:   [5, 2]   и   [8, 1]

внутри левой:  (5,2) - инверсия                       1
внутри правой: (8,1) - инверсия                       1

через границу: сливаем [2,5] и [1,8]
    берём 1 из правой половины → слева ещё остались 2 и 5 → +2 инверсии
    берём 2 из левой           → ничего не прибавляем
    берём 5 из левой           → ничего
    берём 8 из правой          → слева не осталось ничего → +0
                                                          итого через границу 2

всего: 1 + 1 + 2 = 4

Проверим перебором: пары (5,2), (5,1), (2,1), (8,1) - четыре. Сходится.

Смотри, что здесь играет роль «полосы»: ничего геометрического, но структура та же. Пары внутри половин посчитаны рекурсией, пары через разрез - одним линейным проходом, попутно с обычным слиянием. Именно поэтому эта задача уже встречалась в разделе про рекуррентности: она и есть сортировка слиянием с одним дополнительным счётчиком.

Разбор: почему в многомерии всё разваливается

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

На плоскости опасная зона была ограничена с двух сторон, и обе границы взялись из разных мест: по x зону сужала полоса (2d - по d в каждую сторону от разреза), по y - порядок сканирования (d вперёд по отсортированному списку). Осей всего две, и обе оказались связаны - отсюда прямоугольник 2d × d и восемь квадратов.

плоскость:  ось x  - ограничена полосой         → 2d
            ось y  - ограничена сканированием   → d
            итого замкнутый прямоугольник 2d × d, 8 квадратов со стороной d/2

три оси:    ось x  - ограничена полосой         → 2d
            ось z  - ограничена сканированием   → d
            ось y  - НЕ ОГРАНИЧЕНА НИЧЕМ        → зона бесконечна

Вот и вся беда: в трёх измерениях связать удаётся по-прежнему только две оси, а третья остаётся свободной, и опасных точек может быть сколько угодно. Никакого «шестнадцать кубиков» из этого не выводится - доказательство обрывается на первом же шаге.

Поэтому в многомерии деление пополам заменяют СЕТКОЙ с ребром d: точка может оказаться ближе d только к точкам своей клетки и соседних, а соседних клеток 3^k − 1.

клеток на одну точку:  k = 2 → 3² = 9      k = 3 → 3³ = 27
                       k = 10 → 59 049     k = 20 → 3²⁰ ≈ 3.5·10⁹

Пока k мало, это отличная замена: девять клеток на плоскости - та же константа, что «семь соседей». Но константа растёт как 3^k, и «линейное» объединение дешевле перебора пар только пока n больше этой константы. При k = 20 пришлось бы иметь больше семи миллиардов точек, чтобы сетка окупилась, - на любых реальных данных честный перебор пар быстрее.

Это частный случай общего явления, которое называют проклятием размерности: в пространстве большой размерности «близко» перестаёт быть редкостью, объём сосредотачивается у границ, и геометрические приёмы, очевидные на плоскости, ломаются. Практический ответ на это - не улучшать деление, а менять структуру: kd-деревья работают до десятка измерений, дальше применяют приближённые методы вроде хеширования, чувствительного к близости.

Что ломается без этого

Первое: пытаться применить деление пополам к задаче с перекрывающимися подзадачами - получится экспонента вместо линии. Второе: думать, что «через границу» всегда считается за линию: у выпуклой оболочки поиск касательных линеен только при аккуратной реализации, наивный поиск даёт n² и убивает схему. Третье: переносить константу 7 в трёхмерие - там она другая, и с ростом размерности растёт экспоненциально. Четвёртое: забывать, что рандомизированный O(n) для ближайшей пары - ОЖИДАЕМОЕ время, а не гарантия; там, где нужна гарантия, остаётся n·log n. Пятое: выбирать kd-дерево для данных большой размерности: на сотне измерений оно вырождается в полный перебор, только с накладными расходами.

Зачем это в работе

Список задач выше - это половина типовых вопросов на собеседованиях по алгоритмам, и узнавание схемы экономит время: увидел «посчитать пары», «построить силуэт», «найти пересечения» - сразу проверь, распадается ли ответ на «внутри половин» плюс «через границу». В продуктовой разработке прямее всего пригождается родственная идея - пространственная индексация: сетка для поиска ближайших объектов на карте, kd-дерево для рекомендаций по признакам, приближённый поиск соседей для векторных баз. И полезно помнить границу применимости: всё это отлично работает на двух-трёх измерениях и плохо - на сотнях, а векторные представления текста как раз сотнемерные, поэтому там и живут приближённые методы.

Теперь сам

Дан массив [3, 1, 4, 2]. Посчитай число инверсий делением пополам: внутри половин и через границу.

внутри левой:  пара (3,1) - инверсия                  1
внутри правой: пара (4,2) - инверсия                  1

через границу: сливаем отсортированные [1,3] и [2,4]
    берём 1 из левой  → +0
    берём 2 из правой → слева осталось ещё 3 → +1
    берём 3 из левой  → +0
    берём 4 из правой → слева не осталось → +0
                                          итого через границу 1

всего: 1 + 1 + 1 = 3