Cosmin Negruseri tiene toda la razón: la operación debe ser binaria y asociativa. Hay una cosa más a tener en cuenta si queremos que el árbol de segmentos sea eficiente, ver a continuación).
Eso significa que su conjunto de valores (que podría ser algo mucho más complejo que los enteros) debería ser un semigrupo arbitrario. Tenga en cuenta que ni siquiera necesita un elemento neutral, pero su existencia hace que la implementación sea más simple, de lo contrario, tendría que extender artificialmente su semigrupo a la implementación del árbol de segmentos dentro del monoide.
Sin embargo, una restricción más: para ser eficiente, su operación debería ser posible implementar en O (1). En particular, significa que los elementos de su semigrupo deben ocupar espacio O (1). Si su operación tarda T (n) tiempo en computarse, entonces todas las operaciones con árbol de segmentos serán T (n) veces más lentas.
- ¿Cómo implementaría el aumento de precios utilizando estructuras de datos?
- ¿Qué es una cola prioritaria?
- ¿Cuáles son los mejores algoritmos de partición de gráficos para gráficos grandes?
- ¿Cuál es el algoritmo más extraño que hayas usado?
- En términos simples, ¿qué es la complejidad del tiempo amortizado?
Algunos ejemplos de qué árbol de segmentos puede calcular lo siguiente en cualquier subsegmento de una matriz cambiante, en línea, en tiempo logarítmico:
- Elemento máximo y mínimo simultáneamente.
- Posiciones de máximo y mínimo
- Recuentos de valores máximos y mínimos.
- Si se clasifica o no un subsegmento
- Si tratamos el subsegmento como un número escrito en binario, podemos calcularlo como módulo de cualquier constante (es decir, esta constante debe elegirse antes de construir un árbol de segmentos).
- El subsegmento más largo de un subsegmento que contiene solo ceros: su longitud y sus extremos.
