Supongamos que tenemos este problema.
Dado el conjunto A, tenemos que realizar transformaciones Q en ese conjunto de 2 tipos, [math] delete (i), insert (v, i) [/ math]. Elimine el elemento en el índice [math] i [/ math] e inserte el elemento con el valor [math] v [/ math] en el índice [math] i [/ math].
Puede echar un vistazo a que el vector STL implementa dicha funcionalidad, pero lleva tiempo lineal actualizar la matriz. Digamos que no podemos soportar eso, digamos que necesitamos este tipo de operaciones para ejecutarse en [math] O (log (n)) [/ math] time, donde n es el número de elementos en la matriz.
- ¿En qué consiste el pensamiento algorítmico?
- Cómo comprar un algoritmo de creación de mercado para acciones
- Cómo crear mi propio algoritmo de compresión básico para archivos
- ¿Cómo verifico si un número binario es divisible por decir 'n'?
- Cómo mejorar mis algoritmos de clasificación
Una posible solución sería crear un árbol binario que represente la matriz. Y ahí es donde entra en juego la clave implícita. El índice de matriz será nuestra clave implícita, es decir, consideramos un elemento mayor si tiene un índice de matriz mayor. En nuestro árbol, eso significa que si tomamos k elementos más pequeños, obtendremos elementos con índices [math] [0..k-1] [/ math]
Supongamos que tenemos dos funciones [math] merge (ltree, rtree) [/ math] y [math] split (tree, k) [/ math]. La función [math] merge (ltree, rtree) [/ math] combina dos árboles, [math] ltree [/ math] y [math] rtree [/ math], suponiendo que cada elemento en [math] rtree [/ math] es mayor que cualquier elemento en [math] ltree [/ math]. La función devuelve un nuevo árbol combinado.
La función [math] split (tree, k) [/ math] devuelve dos árboles, [math] ltree [/ math] y [math] rtree [/ math], [math] ltree [/ math] que contiene k elementos más pequeños del árbol y [math] rtree [/ math] que contiene el resto del árbol.
Aquí están las funciones de borrar e insertar implementadas usando las funciones de división y fusión.
def borrar (i, a):
left, right = split (a, i) # árbol izquierdo que contiene inices [0..i-1], right one [i..n-1]
_, wright = split (r, 1) # eliminando elemento en el índice i
volver fusión (izquierda, derecha)
def insert (v, i, a):
izquierda, derecha = división (a, i)
return merge (merge (left, new_elem (v)), right)
Si podemos implementar esas funciones para realizarlas en [math] O (log (n)) [/ math] time, tenemos solución a nuestro problema.
Aquí es donde entra en juego Treap, la prioridad del elemento no cambia las posiciones relativas de los elementos, es decir, si el elemento x es mayor que y, seguirá siendo “correcto” en el árbol con respecto al elemento y. Treap asegurará que la complejidad de las operaciones de división y fusión permanezca [matemática] O (log (n)) [/ matemática] a lo largo del tiempo.
Ahora solo tenemos que implementar fusionar y dividir.
Aquí hay un extracto del código C ++ donde hago eso.
fusión de nodo (nodo l, nodo r) {
if (! l ||! r) return (! l)? r: l;
nodo ans = 0;
if (l-> prior> r-> prior) {
l-> r = fusionar (l-> r, r);
ans = l;
} más {
r-> l = fusionar (l, r-> l);
ans = r;
}
volver ans;
}
división vacía (nodo t, int k, nodo & l, nodo & r) {
si t ) {
l = r = 0;
regreso;
}
int clave = getcnt (t-> l);
if (clave <k) {
split (t-> r, k-key-1, t-> r, r);
l = t;
} más {
división (t-> l, k, l, t-> l);
r = t;
}
}
La función [math] getcnt (t) [/ math] devuelve el tamaño del árbol [math] t [/ math], es decir, el número de nodos en ese árbol. Esa es nuestra clave implícita.
Usando este enfoque algo modificado, podemos resolver problemas como revertir alguna submatriz en el tiempo O (log (n)).
