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.
1 Mi Piace
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.
19 Mi Piace
Ok grazie mille per la risposta