Arbol de Segmentos(ST) es basicamente un arbol binario usado para hacer operaciones como suma, minimo, maximo dentro de intervalos o segmentos. Cada nodo en el ST representa un intervalo de L a R por lo tanto el primer nodo del arbol representara al array completo, de lo cual tendremos 3 propiedades basicas.
- La Raiz de arbol representa todo el array A=[0,n]
- Cada hoja del arbol representa un elemento array A=[i] donde 0<i<n
- Una hoja interna del arbol representa A=[L,R] Tenemos que tener claro que una vez creado el Arbol esta estructura no puede ser mnodificado pero tu si puedes podificar los valores de una hoja.
Dado que un ST es un Arbol binario, para la representacion de dicho arbol podemos hacer el uso de un arbol. Un ST puede ser construido de manera recursiva usando Bottom-up approach. Las hojas representan un solo elemento del array, en cada paso el uso de los dos hijos daran el valor del padre, lo que quiere decir que el padre es la union de sus dos hijos. Por lo cual, la raiz del arbol representara el array completo.
- Construccion.O(NlogN)
- Actulizacion. O(log(N+K))
- Consulta. O(log(N+K)) Donde K = Number of retrieved intervals or segments