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

9. Запросы на отрезках

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

Типичные примеры:

  • sumq(a, b) — найти сумму элементов на отрезке [a, b]
  • minq(a, b) — найти минимальный элемент на отрезке [a, b]
  • maxq(a, b) — найти максимальный элемент на отрезке [a, b]

Рассмотрим массив:

индекс:   0  1  2  3  4  5  6  7
значение: 2  5  7  1  6  3  4  8

Для отрезка [2, 6] получаем:

  • sumq(2, 6) = 7 + 1 + 6 + 3 + 4 = 21
  • minq(2, 6) = 1
  • maxq(2, 6) = 7

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

int sum(int a, int b) {
    int s = 0;
    for (int i = a; i <= b; i++) {
        s += array[i];
    }
    return s;
}

Такой подход работает за O(n) на один запрос, где n — размер массива. Если запросов q, то в худшем случае получится O(nq). Когда и массив, и число запросов большие, этого уже недостаточно. Поэтому нужны более быстрые методы.

9.1 Статические запросы к массиву

Сначала рассмотрим случай, когда массив не меняется между запросами. Такой массив называют статическим.

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

Запросы суммы

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

Пусть дан массив:

индекс:   0  1  2  3  4  5  6  7
значение: 4  1  3  9  2  6  5  2

Построим массив префиксных сумм. На позиции k в нём хранится сумма элементов от 0 до k включительно.

индекс:    0  1  2   3   4   5   6   7
префиксы:  4  5  8  17  19  25  30  32

Например:

  • префикс на позиции 3 равен 4 + 1 + 3 + 9 = 17
  • префикс на позиции 6 равен 4 + 1 + 3 + 9 + 2 + 6 + 5 = 30

Как отвечать на запрос суммы

Если мы умеем быстро находить сумму от начала массива до любой позиции, то сумму на произвольном отрезке [a, b] можно получить так:

\[ \operatorname{sumq}(a,b)=\operatorname{sumq}(0,b)-\operatorname{sumq}(0,a-1). \]

Если считать, что

\[ \operatorname{sumq}(0,-1)=0, \]

то формула корректно работает и для случая a = 0.

Пример

Найдём сумму на отрезке [3, 6] в нашем массиве:

индекс:   0  1  2  3  4  5  6  7
значение: 4  1  3  9  2  6  5  2

Непосредственно:

\[ \operatorname{sumq}(3,6)=9+2+6+5=22. \]

Через префиксные суммы:

\[ \operatorname{sumq}(3,6)=\operatorname{sumq}(0,6)-\operatorname{sumq}(0,2)=30-8=22. \]

Именно поэтому после предварительной обработки любой запрос суммы можно обрабатывать за O(1).

Построение префиксных сумм

Префиксный массив строится за O(n):

prefix[0] = array[0];
for (int i = 1; i < n; i++) {
    prefix[i] = prefix[i-1] + array[i];
}

После этого запрос суммы на отрезке можно отвечать так:

int sum(int a, int b) {
    if (a == 0) return prefix[b];
    return prefix[b] - prefix[a-1];
}

Двумерный случай

Идея префиксных сумм обобщается и на двумерные массивы.

Если дана таблица чисел, можно построить двумерный массив префиксных сумм, который позволит за O(1) находить сумму в любом прямоугольнике.

Смысл тот же самый: в каждой клетке хранится сумма элементов от левого верхнего угла до текущей позиции.

Если обозначить четыре области так:

+---------+-----+
|    D    |  B  |
+---------+-----+
|    C    |  A  |
+---------+-----+

то сумма интересующего прямоугольника A выражается через префиксные суммы так:

\[ S(A)=S(\text{общий})-S(B)-S(C)+S(D). \]

Здесь идея полностью аналогична одномерному случаю: лишние области вычитаются, а пересечение возвращается обратно.

Запросы минимума

С запросами минимума всё сложнее. Для сумм сработала разность префиксов, а для минимумов такой трюк уже невозможен.

Тем не менее для статического массива есть эффективный способ:

  • предварительная обработка за O(n \log n)
  • ответ на каждый запрос минимума за O(1)

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

Идея

Предварительно вычислим значения minq(a, b) только для отрезков, длина которых является степенью двойки.

Рассмотрим массив:

индекс:   0  1  2  3  4  5  6  7
значение: 5  2  6  7  1  4  3  8

Сначала вычислим минимумы на отрезках длины 1:

[0,0] -> 5
[1,1] -> 2
[2,2] -> 6
[3,3] -> 7
[4,4] -> 1
[5,5] -> 4
[6,6] -> 3
[7,7] -> 8

Потом длины 2:

[0,1] -> 2
[1,2] -> 2
[2,3] -> 6
[3,4] -> 1
[4,5] -> 1
[5,6] -> 3
[6,7] -> 3

Потом длины 4:

[0,3] -> 2
[1,4] -> 1
[2,5] -> 1
[3,6] -> 1
[4,7] -> 1

И наконец длины 8:

[0,7] -> 1

Всего таких значений будет O(n log n), потому что возможных длин-степеней двойки всего O(log n).

Как вычислять эти значения

Если длина отрезка равна степени двойки, то его можно разбить на две равные половины.

Пусть длина отрезка [a, b] равна 2w. Тогда:

\[ \operatorname{minq}(a,b)=\min\bigl(\operatorname{minq}(a,a+w-1),;\operatorname{minq}(a+w,b)\bigr). \]

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

Как отвечать на любой запрос минимума

Пусть нам нужно найти минимум на отрезке [a, b].

Выберем максимальную степень двойки k, такую что

\[ k \le b-a+1. \]

Тогда ответ можно получить как минимум из двух заранее посчитанных отрезков длины k:

\[ \operatorname{minq}(a,b)=\min\bigl(\operatorname{minq}(a,a+k-1),;\operatorname{minq}(b-k+1,b)\bigr). \]

Заметьте, что эти два отрезка могут пересекаться — это не проблема, потому что минимум от этого не меняется.

Пример

Возьмём тот же массив:

индекс:   0  1  2  3  4  5  6  7
значение: 5  2  6  7  1  4  3  8

Нужно найти минимум на отрезке [1, 6].

Длина отрезка равна 6, наибольшая степень двойки, не превосходящая 6, — это 4.

Значит, берём два отрезка длины 4:

  • [1, 4]
  • [3, 6]

Тогда

\[ \operatorname{minq}(1,6)=\min(\operatorname{minq}(1,4),\operatorname{minq}(3,6)). \]

У нас уже заранее есть:

  • minq(1,4) = 1
  • minq(3,6) = 1

Следовательно,

\[ \operatorname{minq}(1,6)=1. \]

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

  • Подготовка всех минимумов по степеням двойки занимает O(n \log n).
  • Каждый запрос минимума использует только два заранее вычисленных значения.
  • Поэтому ответ на запрос даётся за O(1).

Это один из классических приёмов для статических массивов. Его часто называют sparse table.

Итоги

Для статических массивов можно сильно ускорить запросы на отрезках:

Суммы

  • строим массив префиксных сумм за O(n)
  • отвечаем на запрос за O(1)

Минимумы и максимумы

  • строим таблицу по отрезкам длины 2^k за O(n \log n)
  • отвечаем на запрос за O(1)

Главная идея проста:

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

Эти методы очень полезны в задачах, где массив не меняется, а запросов много.

Небольшое замечание

Как только в задаче появляются изменения элементов массива, префиксных сумм и sparse table уже недостаточно. Тогда нужны более гибкие структуры данных, например:

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