Editar: esta respuesta se basa en la discusión en los comentarios; Mi respuesta original aparece a continuación.
Aquí hay una forma en que creo que puedes hacerlo. Es una publicación larga y estoy bastante seguro de que el método se puede refinar, pero al menos es algo que funciona y tiene un rendimiento razonable.
No estoy muy seguro si solo desea poder insertar nuevos valores al final de la matriz, o también en el medio, pero para mantener las cosas simples, describiré mi solución para las inserciones solo al final. Creo que la estructura también se puede adaptar para admitir inserciones en otras posiciones, si es necesario.
- ¿Cómo crean los algoritmos los programadores de software?
- ¿Debo tomar un curso de estructura de datos y algoritmos antes de aprender cualquier lenguaje de programación? ¿Es importante entender la programación?
- ¿Qué tipo de algoritmo de programación de CPU se utiliza actualmente en los sistemas operativos?
- ¿Cuáles son las aplicaciones prácticas de los diversos algoritmos que estudian los estudiantes de CS en Data Structures?
- ¿Cómo funciona la detección de vandalismo de Wikipedia?
La idea es la siguiente: dividimos la matriz en segmentos [matemáticos] O (\ sqrt n) [/ matemáticos]. La forma en que lo hacemos es la siguiente: supongamos que hemos hecho [math] m [/ math] segmentos hasta ahora, y queremos insertar un nuevo elemento en la matriz de longitud [math] n [/ math]. Si [math] \ sqrt {n} <m [/ math] luego [math] n [/ math], entonces agregamos el nuevo elemento al último segmento. De lo contrario, comenzamos un nuevo segmento y agregamos el elemento a ese nuevo segmento.
Esto tendrá el efecto de que los segmentos cercanos al inicio de la matriz serán más pequeños que los segmentos cercanos al final de la matriz, pero eso no importa: lo que importa es que al final, tendremos [matemáticas] O ( \ sqrt n) [/ math] segmentos, y cada segmento tendrá elementos [math] O (\ sqrt n) [/ math].
El siguiente paso es mantener un índice para todos estos segmentos. Estoy pensando en mantener montones binarios para todos los segmentos. Para cada elemento de la matriz original, mantenemos un puntero a su posición en el montón máximo de su segmento. Ahora, todos estos montones deben mantenerse actualizados bajo asignación, pero eso se puede hacer: si a un elemento de un segmento se le asigna un nuevo valor, tenemos un enlace a su posición anterior en el montón, para que podamos corregir su posición. en [matemáticas] O (\ log n) [/ matemáticas] tiempo. Y de manera similar, podemos mantener estos montones bajo inserción: cada vez que se inicia un nuevo segmento, inicializamos un nuevo montón vacío y le agregamos elementos a medida que se insertan. Por lo tanto, la inserción y la asignación son operaciones [matemáticas] O (\ log n) [/ matemáticas].
Ahora la operación difícil es encontrar el elemento más grande [math] k [/ math] en un intervalo [math] [a, b] [/ math]. Eso se puede hacer de la siguiente manera. Primero, sea sa el índice del primer segmento dividido después de a, y sea sb el índice del último segmento dividido antes de b. Reúna todos los valores de borde en los índices [a, sa) y (sb, b] en una nueva matriz, y construya un montón binario Hborder a partir de él. Esto toma tiempo [matemático] O (\ sqrt n) [/ matemático]. los montones binarios que tenemos para todos los segmentos entre sa y sb, junto con el nuevo montón que contiene los valores de borde. Deseamos encontrar el elemento más grande [math] k [/ math] de todos ellos. Podemos hacerlo mediante poner todos estos montones en otro montón binario H. Este nuevo montón binario “meta” contiene a lo sumo [math] O (\ sqrt n) [/ math] otros montones, o menos, dependiendo de cuántos segmentos se encuentren en el rango [a , b], así que también se puede construir en esa cantidad de tiempo. Ahora repita k veces: elimine el montón de segmento más grande h de H. Luego elimine el elemento más grande de h. Después de [math] k [/ math] pasos , tiene el elemento [math] k [/ math] th más grande que estaba buscando. Esto lleva tiempo [math] O (k \ log n) [/ math]. Después de la consulta, debe volver a insertar todos los valores extraídos en sus montones, lo que lleva la misma cantidad de tiempo que solía extraerlos. (Este último bit en realidad se siente como una pérdida de tiempo, y estoy seguro de que el algoritmo podría refinarse para que este trabajo no sea necesario).
Entonces, el tiempo de ejecución total depende del tiempo requerido para construir Hborder y H, que es como máximo [math] O (\ sqrt {n}) [/ math] para ambos, y el tiempo para extraer [math] k [/ math] el valor más grande, que es [math] O (k \ log n) [/ math]. Entonces, podría argumentar que la estructura de datos en realidad admite dos operaciones: setInterval (a, b), que requiere tiempo de ejecución [math] O (\ sqrt {n}) [/ math], y kthLargest (), que requiere tiempo de ejecución [math] O (k \ log n) [/ math]. Si no tiene que cambiar el intervalo de cada consulta, esto ayudará a reducir aún más el tiempo de ejecución.
Editar: mi respuesta original a continuación se realizó bajo la idea errónea de que el intervalo era un intervalo de valores , en lugar de un intervalo de índices de entrada.
Creo que la forma más fácil es usar un árbol de búsqueda binario, donde en cada nodo interno del árbol [math] n [/ math] se realiza un seguimiento del tamaño del subárbol enraizado en [math] n [/ math].
Si desea encontrar el elemento más grande [math] k [/ math] th en el intervalo [a, b], primero (1) cuente el número [math] s [/ math] de elementos en el árbol que son más pequeños que o igual a [matemáticas] b [/ matemáticas]. Entonces, (2) el elemento que busca es el elemento [math] s-k + 1 [/ math] st en el árbol.
Ambos (1) y (2) se pueden implementar en tiempo [matemático] O (\ log n) [/ matemático] si almacena tamaños de subárbol en todos los nodos internos. Como de costumbre, es posible que desee utilizar un BST equilibrado para garantizar un buen rendimiento.
