Herramientas de usuario
algoritmos-oia:sliding-window-rmq
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:sliding-window-rmq [2017/11/24 22:42] santo |
algoritmos-oia:sliding-window-rmq [2017/11/24 22:42] (actual) santo |
||
|---|---|---|---|
| Línea 284: | Línea 284: | ||
| \end{array} \mbox{, mínimo=$0$}$$ | \end{array} \mbox{, mínimo=$0$}$$ | ||
| - | ¡**Todos** los elementos que había antes quedan dominados por el 0! Entonces, para procesar el ''avanzarB'' debemos sacar de dominantes todos los elementos que queden dominados por el elemento en la posición B, es decir, todos los que sean mayores o iguales que ''v[B]''. Como los dominantes están siempre ordenados, estos elementos que hay que borrar **están todos al final** de la lista de dominantes. Por lo tanto, podemos ir haciendo ''dominantes.pop_back()'' continuamente, mientras el ''dominantes.back()'' sea el índice de un elemento que queda dominado por el de la posición $B$. | + | ¡**Todos** los elementos que había antes quedan dominados por el 0! Entonces, para procesar el ''avanzarB'' debemos sacar de ''dominantes'' todos los elementos que queden dominados por el elemento en la posición $B$, es decir, todos los que sean mayores o iguales que ''v[B]''. Como los dominantes están siempre ordenados, estos elementos que hay que borrar **están todos al final** de la lista de dominantes. Por lo tanto, podemos ir haciendo ''dominantes.pop_back()'' continuamente, mientras el ''dominantes.back()'' sea el índice de un elemento que queda dominado por el de la posición $B$. |
| Lo anterior describe absolutamente todas las ideas de esta implementación. Recomendamos intentar programarla por uno mismo antes de mirar el código de ejemplo que sigue, como práctica de programación. | Lo anterior describe absolutamente todas las ideas de esta implementación. Recomendamos intentar programarla por uno mismo antes de mirar el código de ejemplo que sigue, como práctica de programación. | ||
algoritmos-oia/sliding-window-rmq.1511563344.txt.gz · Última modificación: 2017/11/24 22:42 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
