Semanas 24 y 25 Consultas por Rangos

Semanas 24 y 25: Consultas por Rangos

Objetivo

Practicar estructuras para consultar y actualizar rangos sin recalcular todo el arreglo.

Estado del Avance Actual

• Problemas implementados acumulados: 177.
• Tests automatizados acumulados: 423.
• Módulo agregado: src/patterns/range_queries.rs.
• Tests agregados: tests/range_queries_test.rs.

Problemas Implementados

Problema	Patrón	API
Fenwick Tree	Árbol binario indexado	FenwickTree
Range Sum Query Mutable	Fenwick Tree	RangeSumQuery
Range Minimum Query Mutable	Segment Tree	SegmentTree
Range Add Range Sum Query	Segment Tree con lazy propagation	LazySegmentTree
Difference Array	Incrementos por rango	DifferenceArray
Corporate Flight Bookings	Difference Array	corporate_flight_bookings
Car Pooling	Difference Array	car_pooling
Count of Smaller Numbers After Self	Fenwick Tree + compresión	count_smaller_numbers_after_self
Reverse Pairs	Merge sort + conteo cruzado	reverse_pairs
My Calendar I	Intervalos ordenados	MyCalendar
My Calendar II	Intervalos + dobles reservas	MyCalendarTwo
Range Sum Query 2D Immutable	Prefix sum 2D	RangeSumQuery2D
Range Addition	Difference Array	range_addition
Sliding Window Maximum	Deque monotónica	sliding_window_maximum
Queue Reconstruction by Height	Ordenamiento + inserción	queue_reconstruction_by_height
Snapshot Array	Versionado por índice	SnapshotArray
Count Range Sum	Prefix sum + merge sort	count_range_sum

Ideas Clave

• Prefix sum es suficiente cuando no hay actualizaciones.
• Fenwick Tree permite actualizaciones puntuales y consultas de prefijo en O(log n).
• Una consulta de rango se obtiene restando dos prefijos.
• Range Sum Query Mutable conserva el arreglo original para calcular deltas al actualizar.
• Los valores negativos no cambian el patrón: Fenwick acumula deltas positivos o negativos.
• Segment Tree permite consultar mínimos de rango y actualizar puntos en O(log n).
• Segment Tree es más flexible que Fenwick cuando la operación no se invierte fácilmente.
• Lazy propagation acumula actualizaciones pendientes para no bajar a todos los hijos de un rango completamente cubierto.
• Difference Array convierte varias actualizaciones de rango en marcas de inicio y fin.
• Corporate Flight Bookings usa índices de entrada de 1 a n, por lo que conviene normalizar a base cero.
• Car Pooling usa destino exclusivo: los pasajeros se bajan antes de evaluar los viajes que inician en la misma parada.
• Para contar elementos menores a la derecha, conviene comprimir coordenadas y recorrer el arreglo de derecha a izquierda.
• Fenwick Tree puede contar frecuencias acumuladas cuando los valores originales son grandes o negativos.
• Reverse Pairs se puede resolver con merge sort contando pares cruzados antes de mezclar mitades ordenadas.
• Al comparar nums[i] > 2 * nums[j], conviene promover a i64 para evitar desbordes.
• My Calendar I usa intervalos semiabiertos [inicio, fin); dos eventos pueden tocar frontera sin solaparse.
• Un mapa ordenado permite revisar solo el evento anterior y el siguiente al intentar reservar.
• My Calendar II guarda las zonas doblemente reservadas y rechaza cualquier evento que toque una de ellas.
• Validar índices borde evita resultados silenciosamente incorrectos.
• Range Sum Query 2D usa inclusión-exclusión con cuatro esquinas del prefijo acumulado.
• Sliding Window Maximum mantiene una deque de índices candidatos en orden decreciente por valor.
• Queue Reconstruction ordena por altura descendente para que insertar personas más bajas no altere el conteo k de las más altas.
• Snapshot Array guarda solo cambios por índice y busca el último valor no posterior al snapshot solicitado.
• Count Range Sum cuenta pares de prefijos durante merge sort antes de mezclar mitades ordenadas.

Complejidad

Estructura	Operación	Tiempo	Espacio
Fenwick Tree	construir desde arreglo	O(n log n)	O(n)
Fenwick Tree	actualización puntual	O(log n)	O(1) extra
Fenwick Tree	suma de prefijo	O(log n)	O(1) extra
Range Sum Query Mutable	actualizar y consultar rango	O(log n)	O(n)
Segment Tree	construir desde arreglo	O(n)	O(n)
Segment Tree	actualizar y consultar mínimo	O(log n)	O(n)
Lazy Segment Tree	sumar en rango y consultar suma	O(log n)	O(n)
Difference Array	incremento de rango	O(1)	O(n)
Corporate Flight Bookings	aplicar reservas	O(n + b)	O(n)
Car Pooling	validar capacidad por tramo	O(t + s)	O(s)
Count of Smaller Numbers After Self	contar menores por índice	O(n log n)	O(n)
Reverse Pairs	contar pares durante merge sort	O(n log n)	O(n)
My Calendar I	reservar evento	O(log n)	O(n)
My Calendar II	reservar evento	O(n)	O(n)
Range Sum Query 2D	consultar submatriz	O(1)	O(m * n)
Sliding Window Maximum	máximos por ventana	O(n)	O(k)
Snapshot Array	consultar versión	O(log c)	O(n + c)
Count Range Sum	contar rangos	O(n log n)	O(n)

Siguiente Paso

Continuar con backtracking y combinatoria: variantes con duplicados, particiones y poda.