Intervallo Query minima <O(n), O(1)> approccio (da albero a RMQ limitato)

Question

Quindi, ho letto il tutorial TopCoder this su RMQ (Intervallo query minima) e ho ricevuto una grande domanda.

Sulla sezione dove ha introdotto il approach, cosa posso capire fino ad ora è questo:

(L'intero approccio effettivamente utilizza metodologia introdotta nel Sparse Table (ST) Algorithm, Reduction from LCA to RMQ e from RMQ to LCA)

Dato un array A [N], abbiamo bisogno di trasformarlo in un albero cartesiano, rendendo così un problema di RMQ un problema di LCA (Lowest Common Ancestor). Più tardi, possiamo ottenere una versione semplificata dell'array A e renderlo un problema RMQ limitato.

Quindi sono fondamentalmente due trasformazioni. Quindi la prima parte da RMQ a LCA è semplice. Usando una pila, possiamo trasformare la trasformazione in tempo O (n), ottenendo un array T [N] dove T [i] è l'elemento che è il genitore. E l'albero è completato.

Ma ecco quello che non riesco a capire. L'approccio O (n) richiede un array dove |A[i] - A[i-1]| = 1 e tale array viene introdotto nella sezione Reduction from LCA to RMQ del tutorial. Ciò comporta un Euler Tour di questo albero. Ma come può essere raggiunto con il risultato finale della trasformazione? Il mio approccio ad esso non è lineare, quindi dovrebbe essere considerato negativo in questo approccio, quale sarebbe l'approccio lineare per questo?

UPDATE: Il punto che mi

Here's the array A[]: 

    n : 0 1 2 3 4 5 6 7 8 9 
A[n]: 2 4 3 1 6 7 8 9 1 7 

Here's the array T[]: 

    n : 0 1 2 3 4 5 6 7 8 9 
T[n]: 3 2 0 * 8 4 5 6 3 8 // * denotes -1, which is the root of the tree 

//Above is from RMQ to LCA, it's from LCA to RMQ part that confuses me, more below. 

confondere un quadro della struttura:

A Eulero Tour ha bisogno di conoscere il figlio di ogni nodo, proprio come un DFS (depth Prima ricerca) mentre T [n] ha solo la radice di ciascun elemento, non il figlio.

Answer 1

Qui è la mia attuale comprensione di ciò che si confonde:

1. Al fine di ridurre RMQ a LCA, è necessario convertire l'array in un albero e poi fare un tour di Eulero di quell'albero.
2. Per fare un tour di Eulero, è necessario memorizzare l'albero in modo che ogni nodo punti ai suoi figli.
3. La riduzione elencata da RMQ a LCA ha ogni punto del nodo sul relativo genitore, non sui suoi figli.

Se questo è il caso, le vostre preoccupazioni sono totalmente giustificate, ma c'è un modo semplice per risolvere questo problema. Nello specifico, una volta ottenuta la matrice di tutti i puntatori genitore, è possibile convertirla in un albero in cui ogni nodo punta ai suoi figli in tempo O (n). L'idea è la seguente:

• Creare una matrice di n nodi. Ogni nodo ha un campo valore, un figlio sinistro e un figlio destro.
• Inizialmente, impostare l'ennesimo nodo per avere un figlio nullo a sinistra, figlio nullo a destra e il valore dell'elemento nesimo dall'array.
• Iterare attraverso la matrice T (dove T [n] è l'indice di genitore n) e procedere come segue:
  • Se T [n] = *, allora la voce n è la radice. Puoi conservarlo per un uso successivo.
  • Altrimenti, se T [n] < n, allora sapete che il nodo n deve essere un figlio destro del suo genitore, che è memorizzato nella posizione T [n]. Quindi imposta il figlio destro del nodo T [n] th come l'ennesimo nodo.
  • Altrimenti, se T [n]> n, allora sapete che il nodo n deve essere un figlio sinistro del suo genitore, che è memorizzato nella posizione T [n]. Quindi imposta il figlio sinistro del nodo T [n] th come l'ennesimo nodo.

Questo viene eseguito in tempo O (n), poiché ogni nodo viene elaborato esattamente una volta.

Una volta eseguita questa operazione, hai costruito in modo esplicito la struttura ad albero di cui hai bisogno e hai un puntatore alla radice. Da lì, dovrebbe essere ragionevolmente semplice procedere con il resto dell'algoritmo.

Spero che questo aiuti!