Clase 28/06 Segment Tree: range queries + analisis amortizado de complejidad

[Mariano Crosetti]

La clase anterior empezamos Segment Tree, una de las estructuras de datos más usadas en competencias.

Vimos que Segment Tree aplica a cualquier problema sobre una secuencia que admita una solución por D&C. Y permite hacer toda clase de operaciones como:

• Consultas (sum A[i..j], max A[i..j]).
  
• Más consultas: Cuále es el k-th menor número entre A[i..j].
  
• Consultas re re falopa: Cuál es la suma del subarray de máxima suma entre los indices i y j.

Y a la vez de permitir updates:

• Modificaciones (A[i]=X).
  
• Modificaciones en rango (A[i..j]=x).

TODO en O(log N)

La clase que viene vamos a ver temas avanzados de Segment Tree como:

• Laziness (ya vimos esto para las queries en rango, pero vamos a profundizar).
• Persistencia.
• Analisis de costo amortizado.

Para lo cual vamos a ver analisis de costo amortizado (analizar la complejidad promedio de N operaciones), un tema que no se suele llegar a dar en la currícula y es MUY importante para el análisis de complejidad.

Vamos a ver el método del potencial para análisis amortizado que es una herramienta muy poderosa.

CUANDO? Miércoles 28/06 de 18:30 a 20:30

DONDE? Laboratorio del DCC de FCEIA (Pellegrini 250).

Es muy importante que vengan todos!

Los espero,

Mariano