Data Structure & Algorithms
Preprocesamiento con prefix sums y conteo de frecuencias para consultas de rango, subarrays, matrices, difference arrays y multiplicidades.
Prefix sums y frequency counting hacen un preprocesamiento para responder consultas posteriores sin repetir recorridos.
pagar una vez O(n)
→ reutilizar información en muchas consultasSon ejemplos de un trade-off: usar memoria para reducir tiempo repetido.
Para values = [3, 1, 4, 2], define:
prefix[0] = 0
prefix[1] = 3
prefix[2] = 4
prefix[3] = 8
prefix[4] = 10prefix[i] representa la suma de los primeros i elementos, es decir, el rango semiabierto [0, i).
function buildPrefixSum(values: readonly number[]): number[] {
const prefix = Array(values.length + 1).fill(0);
for (let index = 0; index < values.length; index += 1) {
prefix[index + 1] = prefix[index] + values[index];
}
return prefix;
}El cero inicial elimina casos especiales para rangos que comienzan en 0.
La suma del rango semiabierto [left, right) es:
prefix[right] - prefix[left]function rangeSum(prefix: readonly number[], left: number, right: number): number {
if (left < 0 || right < left || right >= prefix.length) {
throw new RangeError("Invalid half-open range");
}
return prefix[right] - prefix[left];
}¿Por qué funciona?
prefix[right] = suma antes de left + suma de left a right
prefix[left] = suma antes de left
resta = suma de left a rightO(n) tiempo y O(n) memoria;O(1).Sin prefix sum, q consultas pueden costar O(qn). Con preprocesamiento: O(n + q).
Para [left, right] inclusivo:
prefix[right + 1] - prefix[left]Mezclar rangos inclusivos y semiabiertos es una fuente frecuente de off-by-one. Escribe la convención junto a la función.
Funcionan perfectamente con negativos. Lo que puede fallar con negativos es una sliding window que necesita monotonicidad, no el acumulado.
values: [2, -3, 5]
prefix: [0, 2, -1, 4]El prefix ya no es creciente, pero las restas de rangos siguen siendo correctas.
Para un subarray [left, right]:
prefix[right + 1] - prefix[left] = target
prefix[left] = prefix[right + 1] - targetMientras recorres, cuenta cuántos prefijos anteriores tienen el valor requerido.
function countSubarraysWithSum(
values: readonly number[],
target: number,
): number {
const seen = new Map<number, number>([[0, 1]]);
let prefix = 0;
let count = 0;
for (const value of values) {
prefix += value;
count += seen.get(prefix - target) ?? 0;
seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
}
return count;
}0 → 1 representa el prefijo vacío. Permite contar subarrays que comienzan en índice 0.
Tiempo promedio O(n), memoria O(n).
El orden importa: consultas prefijos anteriores antes de registrar el actual para no contar un subarray vacío cuando target === 0.
La técnica no se limita a suma.
xor(left..right) = prefixXor[right + 1] XOR prefixXor[left]Funciona porque x XOR x = 0 y la operación se cancela.
Puedes mantener un prefix por cada categoría para responder cuántas apariciones existen en un rango.
La división de prefix products falla con ceros y puede sufrir precisión u overflow. La operación y su inversa deben ser válidas en el dominio.
No toda operación agregada admite obtener rangos con dos prefijos.
Prefix sums también reconstruyen el efecto de muchas actualizaciones de rango.
Para sumar delta a [left, right]:
difference[left] += delta
difference[right + 1] -= deltaDespués acumula una vez.
function applyRangeUpdates(
length: number,
updates: ReadonlyArray<{
left: number;
right: number;
delta: number;
}>,
): number[] {
const difference = Array(length + 1).fill(0);
for (const update of updates) {
if (
update.left < 0 ||
update.right < update.left ||
update.right >= length
) {
throw new RangeError("Invalid update range");
}
difference[update.left] += update.delta;
difference[update.right + 1] -= update.delta;
}
const result = Array(length).fill(0);
let current = 0;
for (let index = 0; index < length; index += 1) {
current += difference[index];
result[index] = current;
}
return result;
}Cada update cuesta O(1) y la reconstrucción O(n). Es ideal cuando todas las actualizaciones se conocen antes de necesitar valores finales.
No responde eficientemente consultas intercaladas con updates; para eso considera Fenwick o segment tree.
Para matrices, prefix[row][col] puede representar la suma del rectángulo desde el origen hasta antes de esa fila y columna.
rectangle sum
= total superior-izquierdo grande
- región superior
- región izquierda
+ intersección restada dos vecesfunction build2DPrefix(matrix: readonly number[][]): number[][] {
const rows = matrix.length;
const cols = rows === 0 ? 0 : matrix[0].length;
if (matrix.some((row) => row.length !== cols)) {
throw new RangeError("Matrix must be rectangular");
}
const prefix = Array.from(
{ length: rows + 1 },
() => Array(cols + 1).fill(0),
);
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
prefix[row + 1][col + 1] =
matrix[row][col] +
prefix[row][col + 1] +
prefix[row + 1][col] -
prefix[row][col];
}
}
return prefix;
}Una consulta rectangular cuesta O(1) después de O(rows · cols) de preprocesamiento.
Si las claves son enteros densos entre 0 y k - 1, un array es más directo que Map.
function countDigits(values: readonly number[]): number[] {
const counts = Array(10).fill(0);
for (const value of values) {
if (!Number.isInteger(value) || value < 0 || value > 9) {
throw new RangeError("Expected digits from 0 to 9");
}
counts[value] += 1;
}
return counts;
}O(n);O(k), aquí constante porque k = 10.Para dominio disperso o desconocido:
function countValues<T>(values: readonly T[]): Map<T, number> {
const counts = new Map<T, number>();
for (const value of values) {
counts.set(value, (counts.get(value) ?? 0) + 1);
}
return counts;
}Memoria O(k), con k valores distintos.
Un Set solo responde presencia. Un mapa de frecuencias modela un multiset:
[A, A, B] ≠ [A, B]Útil para:
Prefix sums no siempre convienen.
Una consulta única de rango puede resolverse recorriendo el segmento. Construir O(n) datos auxiliares solo se amortiza con suficientes consultas o cuando forma parte de un algoritmo mayor.
Pregunta:
En JavaScript, number representa enteros exactamente solo hasta Number.MAX_SAFE_INTEGER. Una suma grande puede perder precisión sin producir una excepción.
Para enteros grandes puedes usar bigint, pero no mezclarlo directamente con number.
En otros lenguajes, acumulados pueden overflow tipos de 32 bits. El tipo del prefix debe soportar la suma máxima posible.
[i, i);n y añadir ramas especiales innecesarias.Map cuando un array pequeño y denso es mejor, o al revés.prefix[i] debe tener un significado exacto, preferiblemente primeros i elementos.O(1).¿Por qué el mapa de countSubarraysWithSum comienza con la entrada 0 → 1?
Representa el prefijo vacío. Si el acumulado actual es igual al objetivo, prefix - target = 0 y se cuenta correctamente el subarray que comienza en el primer elemento.