algorithm - mas - Estructura de datos para cambiar dinámicamente la secuencia de n longitud con la consulta de longitud de subsecuencia más larga

subsecuencia comun mas larga java

Question

Necesito diseñar una estructura de datos para mantener secuencias de longitud n , con los siguientes métodos:

• increasing() - devuelve la longitud de la subsecuencia en aumento más larga
• change(i, x) : agrega x al elemento i-th de la secuencia

Intuitivamente, esto suena como algo que se puede resolver con algún tipo de árbol de intervalos. Pero no tengo idea de cómo pensar en eso.

Me pregunto cómo usar el hecho, que no necesitamos saber cómo se ve esta subsecuencia, solo necesitamos su longitud ...

Tal vez esto sea algo que pueda usarse, pero estoy bastante estancado en este punto.

Answer 1

Intento explicar mi idea. Puede ser un poco más simple que implementar el árbol de intervalos, y debería proporcionar una complejidad deseable: O (1) para aumentar () y O (logS) para cambiar (), donde S es el conteo de secuencias (puede reducirse a N en el peor de los casos) por supuesto).

Al principio necesitas matriz original. Debe verificar los bordes de los intervalos (utilizaré el intervalo de palabras como sinónimo para secuenciar) después de cambiar (). Deja que sea un

En el segundo necesitas lista bidireccional de intervalos. El elemento de esta lista debe almacenar los bordes izquierdo y derecho. Cada secuencia creciente debe presentarse como un elemento separado de esta lista y estos intervalos deben ir uno tras otro como se presenta en A. Que esta lista sea L. Necesitamos operar punteros en elementos, por lo tanto, no sé si es posible hacerlo en iteradores con contenedor estándar.

En tercer lugar, necesita una cola de prioridad que almacene las longitudes de todos los intervalos en su matriz. Por lo tanto, la función de aumento () se puede hacer con O (1) tiempo. Pero también necesita almacenar el puntero al nodo desde L hasta los intervalos de búsqueda. Que esta cola de prioridad sea PQ . Más formalmente, la cola de prioridad contiene pares (longitud de intervalo, puntero a nodo de lista) con comparación solo por longitud.

A continuación, necesita un árbol, que puede recuperar bordes de intervalo (o rango) para un elemento en particular. Se puede implementar simplemente con std :: map, donde la clave está en el borde izquierdo del árbol, por lo que con la ayuda de map :: lower_bound puede encontrar este intervalo. El valor debe almacenar el puntero al intervalo en L. Deja que este mapa sea MP

Y lo siguiente importante: los nodos de la lista deben almacenar los elementos del elemento correspondiente en la cola de prioridad. Y no debe trabajar con la cola de prioridad sin conexión con el enlace al nodo desde L (cada operación de intercambio en PQ debe actualizar los indecisos correspondientes en L ).

La operación de cambio (i, x) se puede ver así:

1. Encontrar el intervalo, donde se encuentra con el mapa. -> Usted encuentra puntero al nodo correspondiente en L. Por lo tanto, sabes los bordes y la longitud del intervalo
2. Intente comprender qué acciones deben realizarse: nada, intervalo dividido, intervalos de pegamento.
3. Haga esta acción en la lista y asigne un mapa con conexión con PQ . Si necesita un intervalo dividido, elimínelo de PQ (esto no es una operación remove-max) y luego agregue 2 nuevos elementos a PQ . Similar a si necesita pegar intervalos, puede eliminar uno de PQ y hacer aumentar la clave a segunda.

Una dificultad es que PQ debe admitir la eliminación de elementos arbitrarios (por índice), por lo que no puede usar std :: priority_queue, pero no es difícil de implementar, como creo.

Answer 2

LIS se puede resolver con árbol, pero hay otra implementación con programación dinámica, que es más rápida que el árbol recursivo. Esta es una implementación simple en C ++.

class LIS {
    private vector<int> seq ;
    public LIS(vector<int> _seq) {seq = _seq ;}
    public int increasing() {
        int i, j ;
        vector<int> lengths ;
        lengths.resize(seq.size()) ;
        for(i=0;i<seq.size();i++) lengths[i] = 1 ;

        for(i=1;i<seq.size();i++) {
            for(j=0;j<i;j++) {
                if( seq[i] > seq[j] && lengths[i] < lengths[j]+1 ) {
                    lengths[i] = lengths[j] + 1 ;
                }
            }
        }

        int mxx = 0 ;
        for(i=0;i<seq.size();i++)
            mxx = mxx < lengths[i] ? lengths[i] : mxx ;

        return mxx ;
    }

    public void change(i, x) {
        seq[i] += x ;
    }

}

Answer 3

Esto resuelve el problema solo para intervalos contiguos. No resuelve subsecuencias arbitrarias. :-(

Es posible implementar esto con el tiempo O(1) para el intervalo y O(log(n)) para el change .

En primer lugar, necesitaremos un montón para todos los intervalos actuales, con el mayor en la parte superior. Encontrar el intervalo más largo es solo una cuestión de buscar en la parte superior del montón.

A continuación, necesitamos un montón de información para cada una de nuestras n ranuras.

value: Current value in this slot
interval_start: Where the interval containing this point starts
interval_end: Where the interval containing this point ends
heap_index: Where to find this interval in the heap NOTE: Heap operations MUST maintain this!

¡Y ahora el truco inteligente! Siempre almacenamos el valor para cada ranura. Pero solo almacenamos la información del intervalo para un intervalo en el punto en el intervalo cuyo índice es divisible por la potencia más alta de 2. Siempre hay un solo punto para cada intervalo, por lo que almacenar / modificar esto es muy poco trabajo.

Luego, para averiguar en qué intervalo se encuentra una posición dada en la matriz actualmente, debemos observar a todos los vecinos que están incrementando las potencias de 2 hasta que encontremos la última con nuestro valor. Entonces, por ejemplo, la información de la posición 13 se puede encontrar en cualquiera de las posiciones 0, 8, 12, 13, 14, 16, 32, 64, .... (Y tomaremos el primer intervalo que encontremos en la lista 0, ..., 64, 32, 16, 8, 12, 14, 13 ) Esta es una búsqueda de una lista O(log(n)) por lo que es O(log(n)) trabajo.

Ahora, ¿cómo implementamos el change ?

1. Actualizar el valor.
2. Averigua en qué intervalo estábamos, y si estábamos en un límite de intervalo.
3. Si se cambiaron los intervalos, retire los antiguos del montón. (Podemos eliminar 0, 1 o 2)
4. Si los intervalos se cambian, inserte los nuevos en el montón. (Podemos insertar 0, 1 o 2)

Esa actualización es muy compleja, pero es un número fijo de operaciones O(log(n)) y, por lo tanto, debería ser O(log(n)) .