Запросы к массиву

Запрос к массиву — это вопрос о его элементах: найти сумму или количество на отрезке, определить среднее, максимум, минимум или число элементов, удовлетворяющих условию. Главный приём темы — заранее построить вспомогательный массив префиксных значений, чтобы каждый запрос обрабатывался за \(O(1)\), а не перебирал все элементы заново.

Модель запроса и индексы

Пусть дан массив \(a_1,a_2,\ldots,a_n\). Запрос обычно задаёт отрезок индексов от \(l\) до \(r\), причём оба конца включаются. Например, запрос «найти сумму элементов с 3-го по 7-й» означает \(a_3+a_4+a_5+a_6+a_7\). В программировании индексы могут начинаться с нуля, поэтому важно заранее решить, какую нумерацию использует условие и код.

Если запросов немного, каждый можно обработать обычным циклом. Но при большом числе запросов такой способ медленный: один длинный отрезок требует до \(n\) операций. Для сумм и количеств применяют кумулятивную сумму, которую также называют префиксной суммой.

Префиксная сумма и сумма на отрезке

Префиксная сумма \(p_i\) — сумма первых \(i\) элементов массива. Удобно добавить нулевой элемент \(p_0=0\). Тогда \(p_i\) содержит сумму \(a_1+a_2+\ldots+a_i\).

Сумму на отрезке \([l;r]\) получаем вычитанием: из суммы первых \(r\) элементов убираем сумму первых \(l-1\) элементов. Это и есть основной ответ для суммы на отрезке.

Количество элементов на отрезке

Чтобы быстро считать элементы, удовлетворяющие условию, строят не сумму самих значений, а сумму индикаторов. Для каждого элемента задаём \(b_i=1\), если условие выполнено, и \(b_i=0\) в противном случае. Префиксные суммы массива \(b\) дают количество подходящих элементов на любом отрезке.

Например, для подсчёта чётных элементов условие \(a_i\bmod 2=0\). Для подсчёта положительных элементов — \(a_i>0\). Такой подход связан с условным счётчиком, но префиксный массив позволяет отвечать на запросы сразу для разных отрезков.

Ответ: сумма на \([2;5]\) равна \(10\), а положительных элементов на \([1;4]\) — \(2\).

1a = [4, -2, 7, 0, 5, 3]
2n = len(a)
3p = [0] * (n + 1)
4for i in range(1, n + 1):
5    p[i] = p[i - 1] + a[i - 1]
6
7l, r = 2, 5
8segment_sum = p[r] - p[l - 1]
9
10q = [0] * (n + 1)
11for i in range(1, n + 1):
12    q[i] = q[i - 1] + (1 if a[i - 1] > 0 else 0)
13positive_count = q[4] - q[0]

Среднее, максимум и несколько условий

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

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

Реализация и оценка сложности

При нумерации с нуля часто используют массив префиксов длины \(n+1\): \(p[0]=0\), а элемент \(a[i]\) добавляют в \(p[i+1]\). Тогда сумма элементов с индексами \(l\) до \(r\) включительно равна \(p[r+1]-p[l]\). Такая запись уменьшает число особых случаев, особенно для отрезка, начинающегося с первого элемента.

Построение одного префиксного массива требует \(O(n)\) времени и \(O(n)\) памяти. После этого каждый запрос суммы или количества занимает \(O(1)\). Если запросов \(m\), общая сложность равна \(O(n+m)\) вместо \(O(nm)\) в худшем случае при полном переборе каждого отрезка.

Связь с другими задачами

В задачах экзамена запросы могут быть спрятаны в условии: например, нужно обработать много строк, найти пары или тройки элементов, подсчитать символы с нужным свойством или вычислить условную сумму. Для строк тот же принцип работает после замены символа на индикатор: \(b_i=1\), если символ подходит, и \(0\) иначе. Для более сложных условий пригодится обработка массива по условию, а для суммы только подходящих значений — условная сумма.