HOY en Estructuras de Datos Piolas: Segment Tree

[Mariano Crosetti]

La clase de hoy va a ser sobre Segment Tree, una de las estructuras de datos más usadas en competencias.

El Segment Tree permite dado una lista de números, por ejemplo hacer:

- Modificaciones (A[i]=X).

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

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

- Más consultas: Cuál es la suma del subarray de máxima suma entre los indices i y j.

TODO en O(log N)

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

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

La clase va a tener 1 hora con un nivel más introductorio y 1 hora con un nivel más avanzado. Es muy importante que vengan todos!

Los espero,

Mariano