Strutture dati varie


#1

Ciao a tutti, volevo chiedervi alcuni consigli. Conosco il fenwick tree e il segment tree, e vorrei imparare una nuova struttura dati. So che ce ne sono moltissime (es bst, bbst, heap, treap e sicuramente molte altre che non ho mai sentito), solo che non so nulla riguardo ad esse e avrei bisogno di alcuni consigli. Ad esempio quali sono le più utili per le olimpiadi? Sono tutte importanti o alcune possono essere “lasciate indietro” perché non utili/ ne esistono altre che fanno le stesse cose in modo migliore? Da quale mi consigliate di iniziare? Sapreste indicarmi dove poterle studiare in modo abbastanza approfondito?
Grazie.


#2

Ecco un breve elenco.

BST

Sono inutili, servono solo nella teoria.

BBST

Sono già implementati all’interno della stl sotto il nome di std::set. Sono particolarmente utili perché supportano le funzioni insert, erase, lower_bound e upper_bound con complessità \mathcal O(\log N). Consiglio di leggere la documentazione.

Heap

Anche questi sono già implementati nella stl sotto il nome di std::priority_queue. In poche parole sono dei BBST che supportano solo inserimento ed estrazione dell’elemento minore. Si usano perché sebbene abbiano la stessa complessità sono molto più veloci nella pratica.

Treap, skip list

Fino a due anni fa si pensava che queste strutture dati fossero escluse dal syllabus delle OII, poi è arrivato specchi. Se non punti ad arrivare primo puoi ignorare queste strutture dati.

Binary lifting

L’applicazione principale è il LCA, è abbastanza semplice da imparare e fa comodo conoscerlo.

Sparse table

Struttura dati molto carina che permette di ottenere il minimo o il massimo in un intervallo in tempo costante. In alternativa si può usare un classico segment tree, anche se è meno efficiente.

Union-find disjoint sets

Davvero utili soprattutto se combinate con i treap soprattutto nei grafi. Sono una delle strutture dati che bisogna conoscere.

Min/max queue

Questo commento dovrebbe essere abbastanza esaustivo.

Trie, suffix tree, suffix array

Le strutture dati e in generale gli algoritmi sulle stringhe dovrebbero essere esclusi dal syllabus delle OII. In ogni caso è bene citare queste strutture dati.

Fully dynamic CHT, Li Chao tree

Queste strutture dati sono sicuramente utili, ma non so quanto convenga impararsele.

Link-cut tree

Questa direi proprio di no.

Y-fast trie

Questa esiste solo nella teoria.


#3

Ok grazie mille per la risposta