Post segment trees

[andreshp]

Post sobre Segment Trees, una estructura de datos que permite hacer consultas sobre información de los subintervalos de un vector.

Toda aportación es bienvenida :)

PD: Iré añadiendo más problemas estos días.

[mroman42]

He hecho una primera lectura por encima. Me gustaría hacer después una revisión más amplia, pero el artículo se ve por encima muy bien. Tengo una duda que no sé si es errata o que lo estoy entendiendo mal:

• Las imágenes 1 y 2 representan el árbol resultante del ejemplo, pero en lugar de tener en los nodos los números del ejemplo, tienen el valor genérico sin sustituir (V[0,7] por 1, por ejemplo).

Imagino que va a tardar un tiempo en revisarse mientras estemos de exámenes. Pero quizá alguien de tercero o cuarto que ya haya pasado por ED puede echarle un ojo. @fdavidcl @NCordon @m-andres @JCEntrena

[mroman42]

Otros cambios que me gustaría hacerle:

• En el ejemplo de Segment trees, se escribe el valor de V = [3,2,8,5...] pero no se utiliza inmediatamente, sino que se explica cómo expresar [2,7] como unión de intervalos y luego se usa. Para que fuera más claro y no se mezclaran los números del vector con los números indicando posiciones en el vector, propongo que se hable de un V genérico mientras se calcula V[2,7] y que se dé después el valor de V justo antes de calcular el mínimo, donde se dice: En el ejemplo anterior.
• El título se me hace muy largo y con mucha mayúscula. Voy a proponer cambiarlo a Segment Trees. Al fin y al cabo, el Range Minimum Query aparece en el artículo como una motivación. Esto es mejor que lo decida @andreshp.
• Me he leído el código, pero sólo por encima. A lo mejor se me ha escapado algo.

Con esto, y esperando una segunda revisión, lo veo listo para publicar.

[fdavidcl]

El post tiene muy buena pinta :grinning:; algunos apuntes:

• Cuando se dice que "l pertenece a _{0,1,…, log2 n}", ya se ha definido n como 2^m, así que podríamos simplemente poner {0,1,…, m} y facilitar el entendimiento (?).
• La notación de concatenación de vectores con el símbolo de unión conjuntista, ¿se usa en otros sitios? Es que la veo un poco rara por eso de que los vectores han de mantener el orden y estamos acostumbrados a que en la unión dé igual.
• Sobre las mayúsculas del título, propondría algo como Segment trees y Range minimum query, aunque el de Mario también me parece bien.
• He mirado el código y no he visto nada raro, aunque Python no es mi fuerte, podría haber pasado algo por alto.
• Una tontería: donde enlazas al archivo en Python, podría estar bien que el enlace ocupara varias palabras, por ejemplo archivo en Python en vez de sólo archivo.

Arreglos del blog a raíz de esto: hay que darle más color a los enlaces, que cuesta encontrarlos, y resubir el CSS de highlight.js que hemos perdido el resaltado de código (?). Lo comento por si alguien tiene algo que sugerir. Lo haré luego.

[mroman42]

• A mí no me termina de parecer mal el símbolo conjuntista de unión. No porque no quede raro sino porque todo lo demás me parece más raro. En Haskell se usa ++ para la concatenación. A lo mejor se puede escribir con esto: http://math.stackexchange.com/a/1154439/85067 Pero casi mejor que lo decida @andreshp. Dejarlo con la unión no me parece mal si no encontramos nada mejor. En el enlace también se explican otras alternativas que tampoco me convencen para este caso.

[andreshp]

Pensé en el símbolo conjuntista de la unión para indicar la unión de subintervalos contiguos del vector ([i,j] U [j+1,k] = [i,k] hace que parezca natural). Pero es verdad que con la nomenclatura V[i,j] U V[k,l] queda raro. Voy a revisar el post y a ver si se me ocurre algo.

[andreshp]

Ya he terminado de revisarlo. He cambiado el orden en varios aspectos de la redacción, añadido otro problema, etc.

Al final he utilizado ++ como símbolo para la concatenación de subintervalos (creo que es el único con el que no hay ambigüedades) pero de todas formas solo aparece en una línea.

¡Gracias a los dos!

¿Alguien puede leerlo por última vez?

[fdavidcl]

Solamente esas pequeñas correcciones de formato sin importancia. Por mi parte ninguna pega más. Lo dejo por si Mario (o alguien más) quiere mirarlo de nuevo, y si no hay más que mirar creo que se puede hacer el merge :smile:.

[mroman42]

He hecho un último cambio poniendo en cursiva los dos nombres que se le podían dar al problema y en monoespaciado el nombre de la clase. Quizá habría que poner en cursiva o entre comillas, o algo así todas las expresiones extranjeras, pero como son demasiadas, creo que tiene sentido dejar el resto como están.

Voy a hacer el merge.