Префиксные суммы
Префиксные суммы — это вспомогательный массив, в котором заранее сохранены суммы элементов от начала исходного массива до каждой позиции. С их помощью сумму на любом непрерывном отрезке можно найти за постоянное время, не перебирая все его элементы заново.
Построение
Сначала выполняют перебор элементов массива. Каждый следующий элемент префиксных сумм получают добавлением очередного элемента к предыдущему значению. Для массива \(a\) длины \(n\) создают массив \(P\) длины \(n+1\): \(P_0=0\), а затем вычисляют \(P_i=P_{i-1}+a_i\) для \(i\) от 1 до \(n\). Построение занимает \(O(n)\) времени.
Сумма на отрезке
Если требуется сумма элементов с номерами от \(l\) до \(r\) включительно, используют разность двух префиксных сумм. Из суммы первых \(r\) элементов вычитают сумму первых \(l-1\) элементов — так удаляется левая часть массива.
Пусть массив равен \([3, 1, 4, 2, 5]\). Тогда \(P=[0,3,4,8,10,15]\). Сумма элементов с 2-го по 4-й равна \(P_4-P_1=10-3=7\), то есть \(1+4+2=7\). После построения сумму элементов массива на каждом заданном отрезке можно получать за \(O(1)\).
Формула \(P_r-P_{l-1}\) относится к нумерации с единицы и к отрезку, включающему обе границы. В программировании с индексами от 0 часто используют массив \(P\), где сумма элементов с индексами \(l\) до \(r-1\) вычисляется как \(P_r-P_l\).
Префиксные суммы равны \(P=[0, 5, 8, 10, 14]\). Чему равна сумма элементов с 2-го по 4-й номер?
Главное
- Префиксная сумма \(P_i\) хранит сумму первых \(i\) элементов; удобно начинать с \(P_0=0\).
- Сумма на отрезке \([l,r]\) равна \(P_r-P_{l-1}\) и вычисляется за \(O(1)\).
- Построение префиксных сумм занимает \(O(n)\), поэтому метод особенно полезен при множестве запросов к массиву.