Introducción a las sumas de prefijos

Recursos

Video de YouTube (f0bfiuDjq9A)

Introducción

Las sumas de prefijos (prefix sums) son una técnica para calcular rápidamente la suma de cualquier subarreglo. Al precomputar las sumas acumuladas en tiempo $\mathcal{O}(N)$, las consultas posteriores se pueden resolver en tiempo $\mathcal{O}(1)$. Esta técnica se puede generalizar a operaciones invertibles, como el XOR bit a bit .

Ejemplo - Static Range Sum

Explicación

Supongamos que tenemos un arreglo de enteros $\texttt{arr}$ de tamaño $N$ indexado desde 1 y queremos calcular el valor de

para $Q$ pares distintos $(a,b)$ que cumplen $1\le a\le b\le N$. Usaremos el siguiente ejemplo con $N = 6$:

De forma ingenua, para cada consulta podemos recorrer todas las entradas desde el índice $a$ hasta el índice $b$ y sumarlas. Como hay $Q$ consultas y cada una requiere como máximo $\mathcal{O}(N)$ operaciones para calcular la suma, la complejidad temporal total es $\mathcal{O}(NQ)$. En la mayoría de los problemas de este tipo, las restricciones serán $N, Q \leq 10^5$, así que $NQ$ es del orden de $10^{10}$. Esto no es aceptable; casi con certeza superará el límite de tiempo.

En su lugar, podemos usar sumas de prefijos para procesar estas consultas de suma sobre el arreglo. Designamos un arreglo de sumas de prefijos $\texttt{prefix}$. Primero, como indexamos el arreglo desde 1, asignamos $\texttt{prefix}[0]=0$; luego, para los índices $k$ tales que $1 \leq k \leq N$, definimos el arreglo de sumas de prefijos así:

En esencia, el elemento en el índice $k$ del arreglo de sumas de prefijos almacena la suma de todos los elementos del arreglo original desde el índice $1$ hasta $k$. Esto se puede calcular fácilmente en $\mathcal{O}(N)$ con la siguiente fórmula para cada $1\le k\le N$:

Para el caso de ejemplo, el arreglo de sumas de prefijos queda así:

Ahora, cuando queremos consultar la suma de los elementos de $\texttt{arr}$ entre los índices $a$ y $b$ inclusive (indexados desde 1), podemos usar la siguiente fórmula:

Usando la definición de los elementos del arreglo de sumas de prefijos, tenemos

Como solo consultamos dos elementos del arreglo de sumas de prefijos, podemos calcular sumas de subarreglos en $\mathcal{O}(1)$ por consulta, lo cual es mucho mejor que el $\mathcal{O}(N)$ por consulta que teníamos antes. Ahora, después de un preprocesamiento de $\mathcal{O}(N)$ para calcular el arreglo de sumas de prefijos, cada una de las $Q$ consultas toma tiempo $\mathcal{O}(1)$. Así, la complejidad temporal total es $\mathcal{O}(N+Q)$, que ya debería pasar el límite de tiempo.

Hagamos una consulta de ejemplo y calculemos la suma del subarreglo entre los índices $a = 2$ y $b = 5$, inclusive, en el $\texttt{arr}$ indexado desde 1. Mirando el arreglo original, vemos que esto es

Usando sumas de prefijos:

También se conocen como sumas parciales  (partial sums).

Implementación

Complejidad temporal: $\mathcal{O}(N + Q)$

#include <bits/stdc++.h>
using namespace std;
 
vector<long long> psum(const vector<int> &arr) {
	vector<long long> psums(arr.size() + 1);
	for (int i = 0; i < arr.size(); i++) { psums[i + 1] = psums[i] + arr[i]; }
	// or partial_sum(begin(a), end(a), begin(psums) + 1);
	return psums;
}
 
int main() {
	int N, Q;
	cin >> N >> Q;
	vector<int> nums(N);
	for (int i = 0; i < N; i++) { cin >> nums[i]; }
	vector<long long> prefix_arr = psum(nums);
	for (int i = 0; i < Q; ++i) {
		int l, r;
		cin >> l >> r;
		cout << prefix_arr[r] - prefix_arr[l] << "\n";
	}
}

import java.io.*;
import java.util.*;
 
public class Main {
	static int N, Q;
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(reader.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
 
		st = new StringTokenizer(reader.readLine());
		int[] nums = new int[N];
		for (int i = 0; i < N; i++) { nums[i] = Integer.parseInt(st.nextToken()); }
 
		long[] prefix_arr = psum(nums);
 
		for (int i = 0; i < Q; i++) {
			int l, r;
			st = new StringTokenizer(reader.readLine());
			l = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());
			writer.println(prefix_arr[r] - prefix_arr[l]);
		}
 
		reader.close();
		writer.close();
	}
 
	public static long[] psum(int[] arr) {
		long[] psums = new long[N + 1];
 
		for (int i = 0; i < N; i++) { psums[i + 1] = psums[i] + arr[i]; }
 
		return psums;
	}
}

def psum(arr):
	psums = [0]
	for i in arr:
		psums.append(psum[-1] + i)
	return psums
 
 
N, Q = map(int, input().split())
nums = list(map(int, input().split()))
prefix_arr = psum(nums)
 
for i in range(Q):
	l, r = map(int, input().split())
	print(prefix_arr[r] - prefix_arr[l])

import itertools
 
 
def psum(arr):
	return [0] + list(itertools.accumulate(arr))
 
 
# BeginCodeSnip{Same code as above}
N, Q = map(int, input().split())
nums = list(map(int, input().split()))
prefix_arr = psum(nums)
 
for i in range(Q):
	l, r = map(int, input().split())
	print(prefix_arr[r] - prefix_arr[l])
# EndCodeSnip

Problemas

Quiz