Перейти к содержанию

9.4 Дополнительные приёмы

В этом разделе разберём два полезных приёма для задач на запросы по диапазонам:

  • сжатие индексов;
  • обновления на отрезке через массив разностей.

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

Сжатие индексов

У многих структур данных в основе лежит массив. Это удобно, пока индексы невелики и идут подряд. Но если в задаче встречаются большие координаты, возникает проблема.

Например, пусть нужно работать с позициями:

12, 730, 1000000000

Если пытаться завести массив до индекса 10^9, памяти потребуется слишком много. При этом реально используемых позиций всего три.

Идея

Можно заменить исходные индексы на новые: 1, 2, 3, ..., сохранив их порядок.

Пусть есть функция c(x), которая каждой исходной координате ставит в соответствие новый индекс. Требование одно:

если a < b, то c(a) < c(b)

То есть относительный порядок точек не должен меняться.

Пример

Пусть нужны координаты:

8, 555, 1000000000

Тогда после сжатия можно получить:

c(8) = 1
c(555) = 2
c(1000000000) = 3

Теперь вместо огромных чисел мы работаем с маленькими индексами.

Как делать на практике

Обычно алгоритм такой:

  1. Собрать все координаты, которые вообще появятся в задаче.
  2. Отсортировать их.
  3. Удалить повторы.
  4. Для каждой исходной координаты узнать её позицию в отсортированном списке.

Пример на C++

vector<int> coords = {8, 555, 1000000000, 555};
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());

auto compress = [&](int x) {
    return int(lower_bound(coords.begin(), coords.end(), x) - coords.begin()) + 1;
};

cout << compress(8) << "\n";           // 1
cout << compress(555) << "\n";         // 2
cout << compress(1000000000) << "\n";  // 3

Здесь +1 добавлено, чтобы получить индексацию с единицы — это удобно, например, для дерева Фенвика.

Где это полезно

Сжатие индексов часто встречается в задачах, где:

  • координаты очень большие;
  • реально используемых координат мало;
  • нужно применять Fenwick tree, segment tree или другой массивный каркас;
  • важен порядок координат, а не их точные значения.

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

Обновления на отрезке

До этого обычно рассматриваются структуры, которые умеют:

  • отвечать на запросы по диапазону;
  • изменять одно значение.

Но бывает и обратная ситуация:

  • нужно изменять сразу весь отрезок [a, b];
  • а потом получать значение в одной точке.

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

Массив разностей

Пусть исходный массив такой:

4 4 1 1 1 6 3 3
0 1 2 3 4 5 6 7

Построим массив разностей. Первый элемент оставляем как есть, а дальше записываем разницу между соседними элементами:

4 0 -3 0 0 5 -3 0
0 1  2 3 4 5  6 7

Проверим: если взять префиксную сумму массива разностей, восстановится исходный массив.

Например, значение в позиции 6 равно:

4 + 0 - 3 + 0 + 0 + 5 - 3 = 3

И это действительно значение исходного массива в позиции 6.

Главное наблюдение

Если нужно увеличить все элементы на отрезке [a, b] на x, то в массиве разностей достаточно:

  • прибавить x в позиции a;
  • вычесть x в позиции b+1.

И всё.

Почему это работает

Префиксные суммы массива разностей определяют текущие значения исходного массива.

Если мы добавили x в точке a, то начиная с позиции a все последующие префиксные суммы увеличатся на x.

Если затем вычли x в точке b+1, то начиная с позиции b+1 это увеличение отменится.

Значит, прибавка останется ровно на отрезке [a, b].

Пример

Пусть исходный массив:

4 4 1 1 1 6 3 3

И его массив разностей:

4 0 -3 0 0 5 -3 0

Хотим увеличить все элементы на отрезке [1, 4] на 5.

Тогда меняем только две позиции в массиве разностей:

  • diff[1] += 5
  • diff[5] -= 5

Получаем:

4 5 -3 0 0 0 -3 0

Теперь восстановим исходный массив через префиксные суммы:

4 9 6 6 6 6 3 3

И правда, элементы с индексами от 1 до 4 увеличились на 5.

Как это связано со структурами данных

После такого преобразования задача

  • «прибавить x на всём отрезке [a,b]»
  • «узнать значение в позиции k»

сводится к другой:

  • делать точечные обновления в массиве разностей;
  • считать префиксную сумму до позиции k.

А это уже умеют:

  • дерево Фенвика;
  • дерево отрезков.

То есть вместо сложных диапазонных обновлений можно работать с массивом разностей и обычными точечными изменениями.

Идея в формулах

Если diff — массив разностей, то значение исходного массива в точке k равно:

arr[k] = diff[0] + diff[1] + ... + diff[k]

Если нужно прибавить x на отрезке [a,b], то:

diff[a] += x
diff[b+1] -= x

если b + 1 не выходит за границы массива.

Пример на C++

int n = 8;
vector<int> diff(n + 1, 0);

auto range_add = [&](int a, int b, int x) {
    diff[a] += x;
    if (b + 1 < n) diff[b + 1] -= x;
};

range_add(1, 4, 5);

vector<int> arr(n);
arr[0] = diff[0];
for (int i = 1; i < n; i++) {
    arr[i] = arr[i - 1] + diff[i];
}

Если вместо обычного массива diff использовать Fenwick tree, то можно быстро выполнять много таких обновлений и быстро получать значения в отдельных позициях.

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

Сжатие индексов

Используется, когда координаты большие, но различных координат немного. Мы заменяем реальные значения на компактные номера, сохраняя порядок.

Массив разностей

Позволяет превращать обновление на отрезке в два точечных изменения. После этого значение в позиции восстанавливается как префиксная сумма.

Итог

Оба приёма очень практичны:

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

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