# Strutture dati varie

**URL:** <https://forum.olinfo.it/t/strutture-dati-varie/5772>\
**Category:** Algoritmi\
**Created:** [24 Giugno 2019, 5:48pm UTC](https://forum.olinfo.it/t/strutture-dati-varie/5772 "2019-06-24T17:48:10Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![davide991](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/f6c823/32.png) [@davide991](https://forum.olinfo.it/u/davide991)\
**Post date:** [24 Giugno 2019, 5:48pm UTC](https://forum.olinfo.it/t/strutture-dati-varie/5772/1 "2019-06-24T17:48:10Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [25 Giugno 2019, 12:21am UTC](https://forum.olinfo.it/t/strutture-dati-varie/5772/2 "2019-06-25T00:21:20Z")

</div>

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](https://en.cppreference.com/w/cpp/container/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](https://en.cppreference.com/w/cpp/container/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](https://forum.olinfo.it/t/help-wheel-of-fortune/4612/13) 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.

---

<div class="post-metadata">

**Author:** ![davide991](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/f6c823/32.png) [@davide991](https://forum.olinfo.it/u/davide991)\
**Post date:** [25 Giugno 2019, 7:52am UTC](https://forum.olinfo.it/t/strutture-dati-varie/5772/3 "2019-06-25T07:52:12Z")

</div>

Ok grazie mille per la risposta