Сжатие координат: как превратить значения до 10^9 в индексы массива

Сжатие координат простыми словами: sorted(set) и бинарный поиск, ранги вместо значений, ловушка с пропавшими промежутками, сжатие вместе с запросами, площадь прямоугольников и Count of Range Sum.

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

Коротко

ЧтоСуть
ИдеяЗаменяем каждое значение его номером среди отсортированных уникальных значений
Что сохраняетсяПорядок и равенство: a<b  ⟺  rank(a)<rank(b)a < b \iff rank(a) < rank(b), сами расстояния теряются
СложностьO(nlog⁡n)O(n \log n) на сортировку, дальше O(1)O(1) через словарь или O(log⁡n)O(\log n) через бинпоиск
Когда нужноЗначения до 10910^9, а структура (Фенвик, дерево отрезков, разностный массив) хочет индексы
Главная ловушкаМежду соседними сжатыми точками может пропасть целый промежуток

Зачем это нужно

Многие структуры данных индексируются числами от 00 до n−1n - 1. Дерево Фенвика хранит массив счётчиков, разностный массив — массив разностей, дерево отрезков — массив вершин. Пока значения маленькие, всё просто: значение и есть индекс.

Проблемы начинаются, когда в условии написано «−109≤ai≤109-10^9 \le a_i \le 10^9». Массив на 2⋅1092 \cdot 10^9 ячеек не поместится в память, да и инициализировать его дольше, чем решать задачу. При этом элементов всего n=105n = 10^5, то есть различных значений не больше 10510^5.

Ключевое наблюдение: во многих задачах нам не важны сами значения, важен только их порядок. Сколько элементов меньше текущего? Какой элемент самый большой на отрезке? Пересекаются ли два интервала? На все эти вопросы ответ не изменится, если заменить числа [1000000000, -5, 42, 42, 7] на [3, 0, 2, 2, 1]. Порядок тот же, равные значения остались равными, а индексы стали плотными — от 00 до k−1k - 1, где kk — число различных значений.

Эта замена и называется сжатием координат. Слово «координаты» осталось из геометрии: там сжимают абсциссы и ординаты точек, но приём одинаково работает для любых чисел.

Базовая реализация

Три шага: убрать дубликаты, отсортировать, выдать каждому значению его позицию.

def compress(values: list[int]) -> tuple[list[int], list[int]]: """Возвращает сжатый массив и отсортированный список уникальных значений.""" xs = sorted(set(values)) rank = {x: i for i, x in enumerate(xs)} return [rank[v] for v in values], xs a = [1000000000, -5, 42, 42, 7] compressed, xs = compress(a) print(compressed) # [3, 0, 2, 2, 1] print(xs) # [-5, 7, 42, 1000000000] print([xs[i] for i in compressed] == a) # True

Список xs стоит возвращать вместе с результатом: это обратное отображение. По сжатому индексу i исходное значение восстанавливается как xs[i]. Без него не посчитать, например, длину отрезка или настоящую координату ответа.

Словарь или бинарный поиск

Вместо словаря rank можно искать позицию бинарным поиском:

from bisect import bisect_left def compress_bisect(values: list[int]) -> tuple[list[int], list[int]]: xs = sorted(set(values)) return [bisect_left(xs, v) for v in values], xs

Результат тот же. Словарь даёт O(1)O(1) на поиск, бинпоиск — O(log⁡k)O(\log k), но у бинпоиска есть важное преимущество: он умеет отвечать на вопрос о значении, которого нет в xs. bisect_left(xs, v) — это число сжатых значений, строго меньших v, а bisect_right(xs, v) — число значений, меньших или равных v. Это пригодится, когда нужно найти границы диапазона «от LL до RR», где LL и RR сами в массиве не встречаются.

На практике в Python удобно держать оба инструмента: словарь для значений из исходных данных и bisect для границ запросов.

То же на JavaScript

function compress(values) { const xs = [...new Set(values)].sort((a, b) => a - b) const rank = new Map(xs.map((x, i) => [x, i])) return [values.map((v) => rank.get(v)), xs] } const [compressed, xs] = compress([1000000000, -5, 42, 42, 7]) console.log(compressed) // [ 3, 0, 2, 2, 1 ] console.log(xs) // [ -5, 7, 42, 1000000000 ]

Компаратор (a, b) => a - b обязателен. Без него sort сравнивает числа как строки, и [10, 9, 1].sort() вернёт [1, 10, 9]. Ранги получатся неправильными, а ошибку легко не заметить на маленьких тестах из однозначных чисел.

Сложность

  • Сортировка: O(nlog⁡n)O(n \log n).
  • Построение словаря: O(k)O(k), где k≤nk \le n — число уникальных значений.
  • Преобразование массива: O(n)O(n) со словарём или O(nlog⁡k)O(n \log k) с бинпоиском.
  • Память: O(k)O(k) на xs и словарь.

Итого O(nlog⁡n)O(n \log n), и почти всегда это не узкое место: структура, ради которой мы сжимали, работает за те же O(nlog⁡n)O(n \log n).

Самая простая задача: ранги элементов

На LeetCode есть задача Rank Transform of an Array (1331): заменить каждый элемент его рангом, начиная с единицы, равные элементы получают одинаковый ранг. Это сжатие координат в чистом виде, сдвинутое на один:

def array_rank_transform(arr: list[int]) -> list[int]: rank = {x: i + 1 for i, x in enumerate(sorted(set(arr)))} return [rank[x] for x in arr] print(array_rank_transform([40, 10, 20, 30])) # [4, 1, 2, 3] print(array_rank_transform([37, 12, 28, 9, 100, 56, 80, 5, 12])) # [5, 3, 4, 2, 8, 6, 7, 1, 3]

Обратите внимание на set: если его забыть, у двух двоек будут разные ранги, и последующий подсчёт в дереве Фенвика начнёт путать «меньше» и «меньше или равно».

Сжатие вместе с деревом Фенвика: Count of Range Sum

Классическое применение — подсчёт пар через дерево Фенвика. Подсчёт инверсий и Count of Smaller Numbers After Self подробно разобраны в статье про инверсии, поэтому возьмём задачу посложнее, где сжимать приходится не исходный массив.

Count of Range Sum (LeetCode 327). Дан массив nums и границы lower, upper. Нужно посчитать число подотрезков, сумма которых лежит в [lower,upper][lower, upper].

Переходим к префиксным суммам: сумма отрезка (i,j](i, j] равна pj−pip_j - p_i. Условие превращается в

pj−upper≤pi≤pj−lower,i<j.p_j - upper \le p_i \le p_j - lower, \quad i < j.

Идём по префиксам слева направо и для каждого pjp_j спрашиваем: сколько уже встреченных pip_i попадают в диапазон [pj−upper,pj−lower][p_j - upper, p_j - lower]? Это ровно запрос «сумма на отрезке» к дереву Фенвика, если индексом служит значение префикса.

Префиксные суммы могут быть порядка 101410^{14} и отрицательными, поэтому их сжимаем. А границы pj−upperp_j - upper и pj−lowerp_j - lower в массив префиксов, скорее всего, не входят — здесь и выручает bisect.

from bisect import bisect_left, bisect_right class Fenwick: def __init__(self, n: int): self.t = [0] * (n + 1) def add(self, i: int, delta: int = 1) -> None: i += 1 while i < len(self.t): self.t[i] += delta i += i & -i def prefix(self, i: int) -> int: """Сумма на позициях [0, i).""" s = 0 while i > 0: s += self.t[i] i -= i & -i return s def count_range_sum(nums: list[int], lower: int, upper: int) -> int: pref = [0] for x in nums: pref.append(pref[-1] + x) xs = sorted(set(pref)) fw = Fenwick(len(xs)) ans = 0 for p in pref: # ищем ранние префиксы q с p - upper <= q <= p - lower lo = bisect_left(xs, p - upper) hi = bisect_right(xs, p - lower) ans += fw.prefix(hi) - fw.prefix(lo) fw.add(bisect_left(xs, p)) return ans print(count_range_sum([-2, 5, -1], -2, 2)) # 3

Разберём, почему границы считаются именно так. bisect_left(xs, p - upper) — номер первого сжатого значения, которое не меньше p−upperp - upper. bisect_right(xs, p - lower) — номер первого значения, которое строго больше p−lowerp - lower. Значит, нужные нам сжатые индексы — ровно полуинтервал [lo, hi), и ответ на него — prefix(hi) - prefix(lo). Если подходящих значений нет, lo == hi, и разность равна нулю. Случай lo > hi невозможен, пока lower≤upperlower \le upper.

Решение я проверил на тысяче случайных тестов против перебора за O(n2)O(n^2), включая массивы со значениями до 10910^9. Общая сложность — O(nlog⁡n)O(n \log n).

Сжатие вместе с запросами

Часто в задаче есть два набора чисел: данные и запросы. Например, Number of Flowers in Full Bloom (LeetCode 2251): цветок i цветёт на отрезке [start_i, end_i], человек приходит в момент t, нужно сказать, сколько цветов он увидит. Время — до 10910^9.

Решение через разностный массив: +1 в начале цветения, -1 сразу после конца, затем префиксные суммы. Но разностный массив на 10910^9 ячеек не построить, значит, сжимаем. И вот тут легко ошибиться: если сжать только концы цветения, то момент прихода человека, не совпадающий ни с одним концом, некуда будет поставить.

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

from bisect import bisect_left def full_bloom(flowers: list[list[int]], people: list[int]) -> list[int]: # цветок цветёт на [start, end] включительно -> полуинтервал [start, end + 1) xs = sorted({x for s, e in flowers for x in (s, e + 1)} | set(people)) diff = [0] * (len(xs) + 1) for s, e in flowers: diff[bisect_left(xs, s)] += 1 diff[bisect_left(xs, e + 1)] -= 1 blooming = [] cur = 0 for d in diff: cur += d blooming.append(cur) return [blooming[bisect_left(xs, t)] for t in people] print(full_bloom([[1, 6], [3, 7], [9, 12], [4, 13]], [2, 3, 7, 11])) # [1, 2, 2, 2]

Строго говоря, моменты прихода можно было не добавлять: взять bisect_right(xs, t) - 1 и прочитать значение в ближайшей точке слева, ведь между событиями ничего не меняется. Но вариант «положить в сжатие всё» надёжнее: не надо думать про края, и он без изменений переносится на задачи, где запросы ещё и модифицируют структуру.

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

Главная ловушка: пропавшие промежутки

Сжатие сохраняет порядок точек, но выбрасывает всё, что лежит между ними. Пока мы работаем с точками, это не страшно. Когда работаем с отрезками на целых числах, можно потерять ответ.

Классическая задача — «Плакаты мэра» (известна по POJ 2528). На стену по очереди клеят плакаты, каждый закрывает клетки с l по r включительно. Сколько плакатов видно в конце?

Возьмём плакаты [1, 10], [1, 4], [6, 10]. Первый виден: клетка 5 никем не закрыта. Ответ — 3.

Наивное сжатие концов даёт xs = [1, 4, 6, 10], то есть четыре сжатые клетки. Первый плакат красит клетки 0–3, второй — 0–1, третий — 2–3. Первый полностью закрыт, ответ 2. Клетка 5 исчезла: в сжатом мире 4 и 6 стали соседями.

from bisect import bisect_left def visible_posters_wrong(posters: list[tuple[int, int]]) -> int: xs = sorted({x for l, r in posters for x in (l, r)}) wall = [-1] * len(xs) for color, (l, r) in enumerate(posters): for i in range(bisect_left(xs, l), bisect_left(xs, r) + 1): wall[i] = color return len(set(wall) - {-1}) def visible_posters(posters: list[tuple[int, int]]) -> int: # полуинтервалы [l, r + 1): сжатая ячейка i — это отрезок [xs[i], xs[i + 1]) xs = sorted({x for l, r in posters for x in (l, r + 1)}) wall = [-1] * (len(xs) - 1) for color, (l, r) in enumerate(posters): for i in range(bisect_left(xs, l), bisect_left(xs, r + 1)): wall[i] = color return len(set(wall) - {-1}) posters = [(1, 10), (1, 4), (6, 10)] print(visible_posters_wrong(posters)) # 2 — неверно print(visible_posters(posters)) # 3

Исправление — перейти к полуинтервалам. Плакат [l, r] на целых числах — это то же самое, что полуинтервал [l, r + 1). Сжимаем точки l и r + 1, а сжатой ячейкой i считаем не точку, а промежуток [xs[i], xs[i + 1]). Теперь в примере xs = [1, 5, 6, 11], и промежуток [5, 6) — та самая клетка 5 — становится отдельной ячейкой.

Есть и другой популярный способ: при сжатии добавлять лишнюю точку x + 1 после каждого конца, чтобы «держать» промежуток. Он работает, но удваивает число точек и плохо объясним. Полуинтервалы проще и заодно избавляют от ошибок на единицу в разностных массивах.

Правильная версия здесь красит ячейки в цикле, что даёт O(n2)O(n^2) в худшем случае. В реальном решении вместо цикла стоит дерево отрезков с отложенными операциями или обработка плакатов с конца с системой непересекающихся множеств. Сжатие от этого не меняется.

Сжатие с весами: площадь объединения прямоугольников

Иногда расстояния между точками нужны. Тогда сжимаем, но помним длину каждой сжатой ячейки: xs[i + 1] - xs[i].

Rectangle Area II (LeetCode 850). Даны прямоугольники со сторонами, параллельными осям, координаты до 10910^9. Найти площадь их объединения.

Сжимаем отдельно абсциссы и ординаты всех углов. Получаем сетку не больше 2n×2n2n \times 2n ячеек, причём каждая ячейка либо целиком покрыта каким-то прямоугольником, либо не покрыта вовсе: внутри ячейки нет ни одной границы. Отмечаем покрытые ячейки и складываем их настоящие площади.

def rectangle_area(rects: list[tuple[int, int, int, int]]) -> int: xs = sorted({x for x1, _, x2, _ in rects for x in (x1, x2)}) ys = sorted({y for _, y1, _, y2 in rects for y in (y1, y2)}) xi = {x: i for i, x in enumerate(xs)} yi = {y: i for i, y in enumerate(ys)} covered = [[False] * (len(ys) - 1) for _ in range(len(xs) - 1)] for x1, y1, x2, y2 in rects: for i in range(xi[x1], xi[x2]): for j in range(yi[y1], yi[y2]): covered[i][j] = True area = 0 for i in range(len(xs) - 1): for j in range(len(ys) - 1): if covered[i][j]: area += (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j]) return area print(rectangle_area([(0, 0, 2, 2), (1, 0, 2, 3), (1, 0, 3, 1)])) # 6

Здесь координаты прямоугольников уже полуинтервальные (x1 включительно, x2 нет), поэтому ловушка с пропавшими промежутками не возникает: сжатая ячейка i честно обозначает полосу [xs[i], xs[i + 1]).

Сложность — O(n3)O(n^3): nn прямоугольников, каждый закрашивает до (2n)2(2n)^2 ячеек. Для n≤200n \le 200, как в задаче LeetCode, этого хватает. Решение за O(nlog⁡n)O(n \log n) получается, если по одной оси идти заметающей прямой, а по другой держать дерево отрезков над сжатыми ординатами, которое хранит покрытую длину. Сжатие и там остаётся первым шагом.

Двумерное сжатие и сетки

Тот же приём работает для обходов. Если на плоскости размером 109×10910^9 \times 10^9 стоят несколько сотен стен-прямоугольников и нужно понять, связаны ли две точки, сжимаем обе оси по границам стен (снова с полуинтервалами) и запускаем BFS по сжатой сетке. Каждая сжатая клетка — прямоугольник настоящей плоскости, целиком свободный или целиком занятый, поэтому связность сохраняется.

Если нужна площадь области или длина пути, каждой сжатой клетке приписывают её настоящие размеры — так же, как в задаче про площадь.

Когда сжатие не работает

Онлайн-запросы. Если значения приходят по одному, а ответ нужно выдать до того, как придёт следующее, заранее построить xs нельзя. Варианты:

  • динамическое дерево отрезков, которое создаёт вершины лениво — память O(qlog⁡C)O(q \log C), где CC — диапазон значений;
  • сбалансированное дерево поиска, например декартово дерево, или SortedList из пакета sortedcontainers в Python;
  • если интерактивности на самом деле нет, а запросы просто перечислены во входе, — прочитать всё целиком и сжать. Это частый трюк: задача выглядит онлайн, но решается офлайн.

Нужны расстояния, а не порядок. Сжатие ломает арифметику: после него нельзя проверить aj−ai≤da_j - a_i \le d сравнением рангов. Либо храните xs и сравнивайте настоящие значения, либо ищите границу бинпоиском по xs, как в Count of Range Sum.

Значений мало. Если ai≤105a_i \le 10^5, сжатие не нужно — значение уже годится как индекс. Лишний шаг только добавит место для ошибки.

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

  1. Забыли убрать дубликаты. Без set равные значения получают разные ранги, и запросы «меньше или равно» начинают врать.
  2. Сжали не все точки. Границы запросов, моменты прихода людей, r + 1 для полуинтервалов — всё, где структура будет читаться или писаться, должно быть в xs. Иначе rank[v] упадёт с KeyError, а bisect молча вернёт соседнюю ячейку.
  3. Пропавшие промежутки. Отрезки на целых числах сжимаем как полуинтервалы [l, r + 1), иначе между соседними концами исчезают клетки.
  4. Строковая сортировка в JavaScript. sort() без компаратора сравнивает числа как строки.
  5. Размер структуры. Дерево Фенвика строим на len(xs), а не на n и не на максимальное значение. Для разностного массива нужен ещё один элемент сверху.
  6. Потеряли обратное отображение. Если ответом должна быть настоящая координата или длина, а xs уже выброшен, восстановить её нечем.
  7. Ошибка с bisect_left и bisect_right. Первый даёт число значений < v, второй — <= v. Перепутаете — получите ошибку на единицу ровно в тех тестах, где граница совпадает со значением.

Где встречается на собеседованиях

Отдельной задачи «сожмите координаты» почти не бывает, кроме Rank Transform of an Array. Зато сжатие — обязательный шаг в целом классе задач уровня Hard:

  • Count of Smaller Numbers After Self (315), Reverse Pairs (493), Count of Range Sum (327) — дерево Фенвика по сжатым значениям;
  • Rectangle Area II (850) — сжатие с весами плюс заметающая прямая;
  • Falling Squares (699) и My Calendar III (732) — дерево отрезков над сжатыми концами, если запросы известны заранее;
  • Number of Flowers in Full Bloom (2251) и Describe the Painting (1943) — разностный массив на больших координатах.

На интервью полезно проговорить сжатие вслух: «значения до 10910^9, массив такого размера не построить, но различных значений не больше nn, и нам важен только порядок — сожмём». Это короткая фраза, но она показывает, что вы видите ограничения и понимаете, почему решение влезает в память.

Вопросы, которые могут задать в продолжение:

  • «А если значения приходят потоком?» — динамическое дерево отрезков или сбалансированное BST.
  • «Что изменится, если отрезки закрытые?» — переход к полуинтервалам и история с пропавшими клетками.
  • «Можно ли без словаря?» — да, bisect по xs, ценой лишнего log⁡\log.

Что запомнить

  • Сжатие координат заменяет значения их рангами: O(nlog⁡n)O(n \log n) времени, O(k)O(k) памяти, порядок и равенство сохраняются.
  • Делается офлайн: в xs кладём все точки, которые понадобятся, — и данные, и запросы.
  • bisect_left и bisect_right по xs отвечают на вопросы о значениях, которых в xs нет.
  • Отрезки на целых числах переводим в полуинтервалы, иначе между точками пропадают клетки.
  • Если важны расстояния, храним xs и берём длины ячеек xs[i + 1] - xs[i].

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

Все задачи