Algoritmos y Estructura de Datos

Segment Tree

• Construcción: La complejidad para construir un árbol de segmentos es O(n * log n), donde n es el número de elementos en la secuencia. Esto se debe a que se deben realizar log n iteraciones para construir el árbol completo.
• Consulta: La complejidad para realizar una consulta en un árbol de segmentos es O(log n), ya que solo se necesita una cantidad logarítmica de tiempo para encontrar la información deseada en el árbol.
• Actualización: La complejidad para actualizar un elemento en un árbol de segmentos es O(log n), ya que solo se necesita una cantidad logarítmica de tiempo para actualizar el valor en el árbol.

Interval Tree

• Construcción: La complejidad para construir un árbol de intervalos es O(n * log n), donde n es el número de intervalos en el conjunto. Esto se debe a que se deben realizar log n iteraciones para construir el árbol completo.
• Consulta: La complejidad para realizar una consulta en un árbol de intervalos es O(log n), ya que solo se necesita una cantidad logarítmica de tiempo para encontrar la información deseada en el árbol.
• Actualización: La complejidad para actualizar un elemento en un árbol de intervalos es O(log n), ya que solo se necesita una cantidad logarítmica de tiempo para actualizar el valor en el árbol

Link de apoyo