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: 105.
• Tests automatizados acumulados: 252.
• 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
Difference Array	Incrementos por rango	DifferenceArray
Corporate Flight Bookings	Difference Array	corporate_flight_bookings
My Calendar I	Intervalos ordenados	MyCalendar
My Calendar II	Intervalos + dobles reservas	MyCalendarTwo

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.
• 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.
• 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.
• 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.

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)
Difference Array	incremento de rango	O(1)	O(n)
Corporate Flight Bookings	aplicar reservas	O(n + b)	O(n)
My Calendar I	reservar evento	O(log n)	O(n)
My Calendar II	reservar evento	O(n)	O(n)

Siguiente Paso

Cerrar la fase 4 con repaso y ejercicios mixtos de Fenwick, Segment Tree, Difference Array e intervalos.