Más sobre sumas de prefijos

Suma máxima de subarreglo

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Max Subarray Sum	Fácil	Prefix Sums	en el módulo

Solución - Max Subarray Sum

Consideremos el arreglo de sumas de prefijos $p[0], p[1], \dots, p[n]$ donde $p[i]=\sum_{j=1}^ix_j$ . Entonces la suma del subarreglo $x_{l+1\dots r}$ ( $0\le l < r\le n$ ) es igual a $p[r]-p[l]$ .

Para un extremo derecho fijo $r$ , la suma máxima de subarreglo sobre todos los $l$ válidos es

p[r]-\min_{l < r}{p[l]}.

Así, podemos mantener un mínimo acumulado para guardar $\min\limits_{l < r}{p[l]}$ a medida que iteramos $r$ en orden creciente. Esto da la suma máxima de subarreglo para cada extremo derecho posible, y el máximo entre todos estos valores es nuestra respuesta.

Implementación

Complejidad temporal: $\mathcal{O}(n)$

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
using ll = long long;
 
int main() {
	int n;
	cin >> n;
	vector<long long> pfx(n + 1);  // prefix sum array initially filled with 0's
	for (int i = 1; i <= n; i++) {
		ll x;
		cin >> x;
		pfx[i] = pfx[i - 1] + x;  // compute the prefix sum at each element
	}
 
	ll max_subarray_sum = pfx[1];
	ll min_prefix_sum = pfx[0];
	for (int i = 1; i <= n; i++) {
		// max subarray sum is the maximum difference between two prefix sums
		max_subarray_sum = max(max_subarray_sum, pfx[i] - min_prefix_sum);
		min_prefix_sum = min(min_prefix_sum, pfx[i]);
	}
	cout << max_subarray_sum << endl;
}


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class MaxSubSum {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		read.readLine();
		int[] arr = Arrays.stream(read.readLine().split(" "))
		                .mapToInt(Integer::parseInt)
		                .toArray();
 
		long maxSubSum = arr[0];
		long runningPrefSum = 0;
		long minPrefSum = 0;
		for (int i : arr) {
			runningPrefSum += i;
			maxSubSum = Math.max(maxSubSum, runningPrefSum - minPrefSum);
			minPrefSum = Math.min(minPrefSum, runningPrefSum);
		}
		System.out.println(maxSubSum);
	}
}


size = int(input())
arr = [int(i) for i in input().split()]
assert len(arr) == size
 
max_subarray_sum = arr[0]
min_pref_sum = 0
running_pref_sum = 0
for i in arr:
	running_pref_sum += i
	max_subarray_sum = max(max_subarray_sum, running_pref_sum - min_pref_sum)
	min_pref_sum = min(min_pref_sum, running_pref_sum)
print(max_subarray_sum)

Solución alternativa - Algoritmo de Kadane

El algoritmo de Kadane halla la suma más grande de un subarreglo usando un método voraz. Más información aquí .

Implementación

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

C++JavaPython


#include <iostream>
#include <vector>
 
using namespace std;
using ll = long long;
 
int main() {
	int n;
	cin >> n;
	vector<long long> x(n);
	for (int i = 0; i < n; i++) { cin >> x[i]; }
	ll current_sum = x[0];
	ll max_subarray_sum = x[0];
	for (int i = 1; i < n; i++) {
		/*
		 * Continue the subarray sum or start a new
		 * subarray sum beginning at the current element.
		 */
		current_sum = max(current_sum + x[i], x[i]);
		// Store the maximum subarray sum at each iteration.
		max_subarray_sum = max(max_subarray_sum, current_sum);
	}
	cout << max_subarray_sum << endl;
}


import java.io.*;
import java.util.*;
 
public class MaxSubarraySumKadane {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
 
		long[] x = new long[n];
 
		for (int i = 0; i < n; i++) {  // read input
			x[i] = io.nextInt();
		}
 
		long currentSum = x[0];
		long maxSubarraySum = x[0];
 
		for (int i = 1; i < n; i++) {
			/*
			 * continue the subarray sum or start a new
			 * subarray sum beginning at the current element.
			 */
			currentSum = Math.max(currentSum + x[i], x[i]);
			// store the maximum subarray sum at each iteration.
			maxSubarraySum = Math.max(maxSubarraySum, currentSum);
		}
 
		io.println(maxSubarraySum);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


n = int(input())
 
x = [int(input()) for _ in range(n)]
 
current_sum = x[0]
max_subarray_sum = x[0]
 
for i in range(1, n):
	"""
	Continue the subarray sum or start a new
	subarray sum beginning at the current element.
	"""
	current_sum = max(current_sum + x[i], x[i])
 
	# Store the maximum subarray sum at each iteration.
	max_subarray_sum = max(max_subarray_sum, current_sum)
 
print(max_subarray_sum)

Sumas de prefijos 2D

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Forest Queries	Fácil	2D Prefix Sums	en el módulo

Ahora, ¿qué pasa si queremos procesar $Q$ consultas de la suma sobre un subrectángulo de una matriz 2D con $N$ filas y $M$ columnas? Supongamos que tanto las filas como las columnas están indexadas desde 1, y usamos la siguiente matriz como ejemplo:

0	0	0	0	0
1	5	6	11	8
1	7	11	9	4
4	6	1	3	2
7	5	4	2	3

De forma ingenua, cada consulta de suma tomaría entonces tiempo $\mathcal{O}(NM)$ , para un total de $\mathcal{O}(QNM)$ . Esto es demasiado lento.

Tomemos la siguiente región de ejemplo, cuya suma queremos:

0	0	0	0	0
1	5	6	11	8
1	7	11	9	4
4	6	1	3	2
7	5	4	2	3

Sumando a mano todas las celdas, tenemos una suma de submatriz de $7+11+9+6+1+3 = 37$ .

La primera optimización lógica sería hacer sumas de prefijos unidimensionales de cada fila. Entonces tendríamos la siguiente matriz de sumas de prefijos por fila. La suma deseada del subarreglo de cada fila en nuestra región es simplemente la celda verde menos la celda roja de esa fila. Hacemos esto para cada fila y obtenemos $(28-1) + (14-4) = 37$ .

0	0	0	0	0
1	6	12	23	31
1	8	19	28	32
4	10	11	14	16
7	12	16	18	21

Ahora, si quisiéramos hallar una suma de submatriz, podríamos partir la submatriz en un subarreglo por cada fila y luego sumar sus sumas, que se calcularían con el método de sumas de prefijos descrito antes. Como la matriz tiene $N$ filas, la complejidad temporal de esto es $\mathcal{O}(QN)$ . Esto puede ser suficientemente rápido para $Q=10^5$ y $N=10^3$ , pero podemos hacerlo mejor.

De hecho, podemos hacer sumas de prefijos bidimensionales. En nuestro arreglo de sumas de prefijos bidimensionales, tenemos

\texttt{prefix}[a][b]=\sum_{i=1}^{a} \sum_{j=1}^{b} \texttt{arr}[i][j].

Esto se puede calcular así para el índice de fila $1 \leq i \leq n$ y el índice de columna $1 \leq j \leq m$ :

\begin{aligned} \texttt{prefix}[i][j] =& \, \texttt{prefix}[i-1][j]+ \texttt{prefix}[i][j-1] \\ &- \texttt{prefix}[i-1][j-1]+ \texttt{arr}[i][j] \end{aligned}

Calculemos $\texttt{prefix}[2][3]$ . Probemos el widget interactivo de abajo haciendo clic en los botones para ver qué números se suman en cada paso. Observemos cómo sobrecontamos un subrectángulo, y cómo lo corregimos restando $\texttt{prefix}[i-1][j-1]$ .

Clic en cada paso para aplicarlo. El mouse sobre un paso marca la región.

para obtener prefix[i][j]

00000001561180171194046132075423

La suma de la submatriz entre las filas $a$ y $A$ y las columnas $b$ y $B$ se puede expresar así:

\begin{aligned} \sum_{i=a}^{A} \sum_{j=b}^{B} \texttt{arr}[i][j]=&\,\texttt{prefix}[A][B] - \texttt{prefix}[a-1][B] \\ &- \texttt{prefix}[A][b-1] + \texttt{prefix}[a-1][b-1] \end{aligned}

Al sumar la región azul de arriba con el método de sumas de prefijos 2D, sumamos el valor del cuadrado verde, restamos los valores de los cuadrados rojos y luego sumamos el valor del cuadrado gris. En este ejemplo, tenemos

65-23-6+1 = 37,

como era de esperar.

0	0	0	0	0
1	6	12	23	31
2	14	31	51	63
6	24	42	65	79
13	36	58	83	100

Probemos el widget interactivo de abajo haciendo clic en los botones para ver qué números se suman en cada paso.

Clic en cada paso para aplicarlo. El mouse sobre un paso marca la región.

para obtener el resultado

00000001561180171194046132075423

Como, sin importar el tamaño de la submatriz que estamos sumando, solo necesitamos acceder a cuatro valores del arreglo de sumas de prefijos 2D, esto corre en $\mathcal{O}(1)$ por consulta después de un preprocesamiento de $\mathcal{O}(NM)$ .

Solución - Forest Queries

C++JavaPython


#include <iostream>
#include <vector>
 
using namespace std;
 
constexpr int MAX_SIDE = 1000;
int tree_pref[MAX_SIDE + 1][MAX_SIDE + 1];
int forest[MAX_SIDE + 1][MAX_SIDE + 1];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int N;
	int Q;
	cin >> N >> Q;
	// read in the initial trees
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			char a;
			cin >> a;
			forest[i + 1][j + 1] += a == '*';
		}
	}
 
	// build the prefix sum array
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			tree_pref[i][j] = forest[i][j] + tree_pref[i - 1][j] + tree_pref[i][j - 1] -
			                  tree_pref[i - 1][j - 1];
		}
	}
 
	for (int q = 0; q < Q; q++) {
		int from_row, to_row, from_col, to_col;
		cin >> from_row >> from_col >> to_row >> to_col;
		cout << tree_pref[to_row][to_col] - tree_pref[from_row - 1][to_col] -
		            tree_pref[to_row][from_col - 1] +
		            tree_pref[from_row - 1][from_col - 1]
		     << '\n';
	}
}


import java.io.*;
import java.util.StringTokenizer;
 
public class ForestQueries {
	static int N;
	static int Q;
	static int[][] pfx;
	static int[][] arr;
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		N = io.nextInt();
		Q = io.nextInt();
 
		pfx = new int[N + 1][N + 1];
		arr = new int[N + 1][N + 1];
 
		for (int i = 0; i < N; i++) {
			String line = io.next();
			for (int j = 0; j < N; j++) {
				if (line.charAt(j) == '*') { arr[i + 1][j + 1]++; }
			}
		}
 
		for (int i = 1; i < N + 1; i++) {
			for (int j = 1; j < N + 1; j++) {
				pfx[i][j] =
				    arr[i][j] + pfx[i - 1][j] + pfx[i][j - 1] - pfx[i - 1][j - 1];
			}
		}
 
		for (int i = 0; i < Q; i++) {
			int fromRow = io.nextInt();
			int fromCol = io.nextInt();
			int toRow = io.nextInt();
			int toCol = io.nextInt();
			io.println(pfx[toRow][toCol] - pfx[fromRow - 1][toCol] -
			           pfx[toRow][fromCol - 1] + pfx[fromRow - 1][fromCol - 1]);
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}


side_len, query_num = [int(i) for i in input().split()]
tree_prefixes = [[0 for _ in range(side_len + 1)] for _ in range(side_len + 1)]
for r in range(side_len):
	for ci, c in enumerate(input()):
		tree = c == "*"
		tree_prefixes[r + 1][ci + 1] += (
			tree_prefixes[r][ci + 1]
			+ tree_prefixes[r + 1][ci]
			- tree_prefixes[r][ci]
			+ tree
		)
 
for _ in range(query_num):
	from_row, from_col, to_row, to_col = [int(i) for i in input().split()]
	print(
		tree_prefixes[to_row][to_col]
		- tree_prefixes[to_row][from_col - 1]
		- tree_prefixes[from_row - 1][to_col]
		+ tree_prefixes[from_row - 1][from_col - 1]
	)

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Nusret Gökçe	Normal	Prefix Sums	Solución
CF	Queries for Number of Palindromes	Normal	Prefix Sums	Solución
AC	Sjeltzer?	Normal	Prefix Sums	Solución
Old Silver	The Lazy Cow	Difícil	2D Prefix Sums	Solución
Silver	Rectangular Pasture	Difícil	2D Prefix Sums	Solución
AC	★ Nuske vs Phantom Thnook	Difícil	Trees, 2D Prefix Sums	Solución
Platinum	Modern Art	Muy difícil	2D Prefix Sums	Solución

Arreglos de diferencias

Recursos
Fuente	Recurso	Notas
CF	An Introduction To Difference Arrays

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	Greg and Array	Normal	Difference Array	en el módulo

Explicación - Greg and Array

Creemos un arreglo $s$ , donde $s[i]$ es la cantidad de veces que se aplica la operación $i$ . El paso importante es cómo lo actualizamos.

Para un intervalo $[l, r]$ , no podemos recorrer el intervalo e incrementar cada valor, porque eso sería $\mathcal{O}(MK)$ y demasiado lento. En su lugar, incrementamos $s[l]$ en uno y decrementamos $s[r+1]$ en uno.

Ahora obtenemos el arreglo real calculando su arreglo de sumas de prefijos, lo que resulta en complejidad temporal $\mathcal{O}(M)$ . La segunda parte, aplicar las operaciones, se puede hacer exactamente igual.

Implementación - Greg and Array

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

C++JavaPython


#include <array>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) { cin >> a[i]; }
	vector<array<int, 3>> updates(m);
	for (array<int, 3> &update : updates) {
		cin >> update[0] >> update[1] >> update[2];
	}
 
	vector<long long> s(m + 2);
	vector<long long> add(n + 2, 0);
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		s[x]++;
		s[y + 1]--;
	}
 
	for (int i = 1; i <= m; i++) {
		// Apply prefix sums
		s[i] += s[i - 1];
 
		// At the same time compute the second difference array
		add[updates[i - 1][0]] += s[i] * updates[i - 1][2];
		add[updates[i - 1][1] + 1] -= s[i] * updates[i - 1][2];
	}
 
	for (int i = 1; i <= n; i++) {
		// Apply prefix sums
		add[i] += add[i - 1];
		cout << a[i] + add[i] << ' ';
	}
	cout << endl;
}


import java.util.Scanner;
public class GregArray {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
 
		long[] a = new long[n + 1];
		for (int i = 1; i <= n; i++) { a[i] = sc.nextLong(); }
 
		int[][] updates = new int[m][3];
		for (int i = 0; i < m; i++) {
			updates[i][0] = sc.nextInt();
			updates[i][1] = sc.nextInt();
			updates[i][2] = sc.nextInt();
		}
 
		long[] s = new long[m + 2];
		long[] add = new long[n + 2];
 
		for (int i = 0; i < k; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			s[x]++;
			s[y + 1]--;
		}
 
		for (int i = 1; i <= m; i++) {
			// apply prefix sums
			s[i] += s[i - 1];
 
			// at the same time compute the second difference array
			add[updates[i - 1][0]] += s[i] * updates[i - 1][2];
			add[updates[i - 1][1] + 1] -= s[i] * updates[i - 1][2];
		}
 
		for (int i = 1; i <= n; i++) {
			// apply prefix sums
			add[i] += add[i - 1];
			System.out.print((a[i] + add[i]) + " ");
		}
		System.out.println();
		sc.close();
	}
}


n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
 
updates = []
for _ in range(m):
	updates.append(list(map(int, input().split())))
 
s = [0] * (m + 2)
add = [0] * (n + 2)
 
for _ in range(k):
	x, y = map(int, input().split())
	s[x] += 1
	s[y + 1] -= 1
 
for i in range(1, m + 1):
	# Apply prefix sums
	s[i] += s[i - 1]
 
	# At the same time compute the second difference array
	add[updates[i - 1][0]] += s[i] * updates[i - 1][2]
	add[updates[i - 1][1] + 1] -= s[i] * updates[i - 1][2]
 
for i in range(1, n + 1):
	# Apply prefix sums
	add[i] += add[i - 1]
	print(add[i] + arr[i - 1], end=" ")

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Karen and Coffee	Fácil	Difference Array	Solución
CF	Little Girl and Maximum Sum	Normal	Difference Array	Solución
CF	QED's Favorite Permutation	Normal	Difference Array, Sortings	Solución
SPOJ	★ Haybale Stacking	Normal	Prefix Sums	Solución
Silver	Painting the Barn	Normal	2D Prefix Sums	Solución
Gold	★ Painting the Barn	Difícil	2D Prefix Sums, Max Subarray Sum	Solución

Quiz

Pregunta 1/4

Para una grilla con

N

filas y

M

columnas, ¿cuál es la complejidad temporal ideal para calcular un arreglo de sumas de prefijos 2D de la grilla?