dati per la modifica dinamica sequenza di n-length con query di lunghezza più lunga sottosequenza

Question

Ho bisogno di progettare una struttura di dati per lo svolgimento di n sequenze -Lunghezza, con le seguenti modalità:

• increasing() - restituisce la lunghezza del più lungo crescenti sotto-sequenza
• change(i, x) - aggiunge x per i-esimo elemento della sequenza

Intuitivamente, questo suona come qualcosa risolvibili con un certo tipo di albero dell'intervallo. Ma non ho idea di come pensarlo.

Mi chiedo come utilizzare il fatto, che abbiamo completamente non abbiamo bisogno di sapere come questo sotto-sequenza sembra, abbiamo solo bisogno della sua lunghezza ...

forse questo è qualcosa che può essere usato, ma sono praticamente bloccato a questo punto.

Answer 1

LIS può essere risolto con albero, ma esiste un'altra implementazione con programmazione dinamica, che è più veloce dell'albero ricorsivo. Questa è una semplice implementazione in 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 2

Provo a spiegare la mia idea. Può essere un po 'più semplice dell'implementazione di albero ad intervalli e dovrebbe dare una complessità desiderabile: O (1) per l'aumento(), e O (logS) per change(), dove S è il conteggio delle sequenze (può essere ridotto a N nei casi peggiori ovviamente).

All'inizio è necessario un array originale. È necessario controllare i bordi degli intervalli (userò l'intervallo di parole come sinonimo di sequenza) dopo la modifica(). Let it be A

Al secondo è necessario un elenco bidirezionale di intervalli. L'elemento di questa lista dovrebbe memorizzare i bordi sinistro e destro. Ogni sequenza crescente dovrebbe essere presentata come elemento separato di questo elenco e questi intervalli dovrebbero andare uno dopo l'altro come presentati in A. Lascia che questa lista sia L. Dobbiamo operare dei puntatori sugli elementi, quindi, non so è possibile farlo su iteratori con contenitore standard.

Al terzo è necessaria una coda di priorità che memorizza le lunghezze di tutti gli intervalli nell'array. Quindi, la funzione crescente() può essere eseguita con il tempo O (1). Ma è necessario anche memorizzare il puntatore al nodo da L agli intervalli di ricerca. Lascia che questa coda di priorità sia PQ. Più formalmente la coda di priorità contiene coppie (lunghezza dell'intervallo, puntatore al nodo dell'elenco) con confronto solo per lunghezza.

A questo punto è necessario un albero, in grado di recuperare i bordi dell'intervallo (o intervallo) per un elemento particolare. Può essere semplicemente implementato con std :: map dove key è left border of tree, quindi con l'aiuto di map :: lower_bound puoi trovare questo intervallo. Il valore deve memorizzare il puntatore sull'intervallo in L. Lascia che questa mappa sia MP

E la prossima cosa importante - I nodi di elenco dovrebbero memorizzare gli indizi dell'elemento corrispondente nella coda di priorità. E non si dovrebbe lavorare con la coda di priorità senza connessione con collegamento al nodo da L (ogni operazione di scambio su PQ è necessario aggiornare le indecie corrispondenti su L).

cambiamento (i, x) operazione può essere simile a questo: intervallo

1. Trova, dove ho posizionato con mappa. -> trovi il puntatore al nodo corrispondente in L. Quindi, conosci i confini e la lunghezza dell'intervallo
2. Cerca di capire quali azioni devono essere eseguite: nulla, intervallo di divisione, intervalli di colla.
3. Effettuare questa operazione su elenco e mappa con collegamento a PQ. Se è necessario dividere l'intervallo, rimuoverlo da PQ (questa operazione non è remove-max) e quindi aggiungere 2 nuovi elementi a PQ. Simile se è necessario incollare gli intervalli, è possibile rimuoverne uno da PQ e premere il tasto di incremento al secondo.

Una difficoltà è che PQ dovrebbe sostenere la rimozione elemento arbitrario (per indice), quindi non è possibile utilizzare std :: priority_queue, ma non è difficile da attuare come penso.

Answer 3

Questo risolve il problema solo per intervalli contigui. Non risolve sottosequenze arbitrarie. :-(

E 'possibile implementare questa con il tempo O(1) per l'intervallo e O(log(n)) per change.

Prima di tutto avremo bisogno di un mucchio per tutti gli intervalli di corrente, con la più grande sulla parte superiore. trovare l'intervallo più lungo è solo una questione di guardare in cima al mucchio.

successivo abbiamo bisogno di un po 'di informazioni per ciascuno dei nostri n slot.

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! 

E ora il trucco intelligente! Noi sempre memorizzare il valore per ogni slot. Ma noi solo memorizziamo le informazioni sull'intervallo per un intervallo nel punto dell'intervallo il cui indice è divisibile per la massima potenza di 2. C'è sempre un solo punto per ogni intervallo, quindi archiviare/modificare questo è pochissimo lavoro.

Quindi per capire a quale intervallo si trova attualmente una determinata posizione nell'array, dobbiamo guardare tutti i vicini che stanno aumentando i poteri di 2 finché non troviamo l'ultimo con il nostro valore. Quindi, per esempio, le informazioni sulla posizione 13 possono essere trovate in una qualsiasi delle posizioni 0, 8, 12, 13, 14, 16, 32, 64, .... (E prendiamo il primo intervallo che troviamo nella lista 0, ..., 64, 32, 16, 8, 12, 14, 13.) Questa è una ricerca di una lista O(log(n)) così è O(log(n)) lavoro .

Ora come implementiamo change?

1. Valore di aggiornamento.
2. Calcola l'intervallo in cui ci trovavamo e se eravamo a un limite di intervallo.
3. Se gli intervalli sono stati modificati, rimuovere quelli vecchi dall'heap. (Possiamo rimuovere 0, 1 o 2)
4. Se gli intervalli cambiano, inserire i nuovi nell'heap.(Possiamo inseriamo 0, 1 o 2)

Tale aggiornamento è molto complessa, ma è un numero fisso di O(log(n)) operazioni e quindi dovrebbe essere O(log(n)).