Structdex.cpp

Estructuras de datos para programación competitiva

O(1) O(log n) O(n) O(n log n) O(n²)

Base común

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    return 0;
}
Elegir estructura por necesidad
NecesidadEstructura
Guardar elementos en posiciones numeradas cuando el tamaño no cambiaráArreglo (array)
Guardar elementos en posiciones numeradas cuando la cantidad puede cambiarVector
Guardar, leer y modificar textoCadena (string)
Agregar y quitar elementos rápidamente por ambos extremosCola doble (deque)
Insertar o borrar rápidamente cuando ya conoces la posiciónLista doblemente enlazada (list)
Usar una lista ligera que solo se recorre hacia adelanteLista simplemente enlazada (forward list)
Sacar primero el último elemento que se agregóPila (stack)
Sacar primero el primer elemento que se agregóCola (queue)
Mantener disponible el valor mayor o menor sin ordenar todo manualmenteCola de prioridad
Agrupar dos valores relacionados en una sola variablePar (pair)
Agrupar tres o más valores en una sola variableTupla (tuple)
Guardar valores sin repetirlos y mantenerlos ordenadosSet
Guardar valores sin repetirlos cuando no importa el ordenUnordered set
Guardar valores repetidos y mantenerlos ordenadosMultiset
Guardar valores repetidos cuando no importa el ordenUnordered multiset
Relacionar cada clave con un valor y mantener las claves ordenadasMap
Relacionar claves con valores cuando no importa el ordenUnordered map
Guardar varios valores por cada clave y mantener las claves ordenadasMultimap
Guardar varios valores por clave cuando no importa el ordenUnordered multimap
Guardar una cantidad fija de valores que solo pueden ser 0 o 1Bitset
Guardar, para cada nodo, la lista de nodos conectados directamenteLista de adyacencia
Guardar cada conexión junto con su costo, distancia o pesoGrafo con pesos
Usar una tabla para consultar directamente si dos nodos están conectadosMatriz de adyacencia
Modelar una jerarquía donde cada nodo tiene como máximo dos hijosÁrbol binario
Mantener grupos separados, unirlos y comprobar si dos elementos están conectadosUnion-Find (DSU)
Mantener sumas de prefijo mientras cambian valores individualesÁrbol de Fenwick (BIT)
Consultar rangos mientras se actualizan valores del arregloÁrbol de segmentos
Precalcular mínimos de rangos en un arreglo que no cambiaTabla dispersa (Sparse Table)
Guardar muchas palabras y recorrer sus prefijos carácter por carácterTrie
Ruta de aprendizaje
  1. Secuencias y texto

    array, vector y string.

  2. Agrupar valores

    pair y tuple.

  3. Extremos y prioridades

    deque, stack, queue y priority_queue.

  4. Conjuntos y diccionarios

    set, unordered_set, multiset, unordered_multiset, map y unordered_map.

  5. Bits, listas y grafos

    bitset, list, forward_list y grafos.

  6. Grupos y rangos

    DSU, Fenwick Tree, Segment Tree y Sparse Table.

  7. Árboles y prefijos

    árbol binario y Trie.

Estructuras de datos básicas

Arreglo (array)

Guardar elementos en posiciones numeradas cuando el tamaño no cambiará.

Declaración
array<int, 5> a = {1, 2, 3, 4, 5};
Otras declaraciones
int a[1000] = {}; // 1000 posiciones, todas empiezan en 0
a.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
array<int, 4> a = {10, 20, 30, 40};
cout << a.size(); // imprime 4
a.front()Devuelve el primer elemento. O(1)
Ejemplo
array<int, 3> a = {10, 20, 30};
cout << a.front(); // imprime 10
a.back()Devuelve el último elemento. O(1)
Ejemplo
array<int, 3> a = {10, 20, 30};
cout << a.back(); // imprime 30
a.fill(valor)Pone el mismo valor en todas las posiciones. O(n)
Ejemplo
array<int, 4> a = {1, 2, 3, 4};
a.fill(0); // a = {0, 0, 0, 0}
for (int x : a) cout << x << ' '; // imprime 0 0 0 0
a.begin()Devuelve un iterador: una posición que apunta al primer elemento. O(1)
Ejemplo
array<int, 3> a = {10, 20, 30};
auto it = a.begin();
cout << *it; // imprime 10
a.end()Devuelve la posición que marca el final del recorrido; no contiene un elemento. O(1)
Ejemplo
array<int, 3> a = {10, 20, 30};
auto it = a.end();
--it;
cout << *it; // imprime 30
a.at(i)Acceso con verificación de límites. O(1)
Ejemplo
array<int, 3> a = {10, 20, 30};
cout << a.at(1); // imprime 20
a[i]Acceso directo por índice, sin verificación. O(1)
Ejemplo
array<int, 3> a = {10, 20, 30};
a[1] = 99; // a = {10, 99, 30}
cout << a[1]; // imprime 99

i debe estar entre 0 y size() - 1.

Vector

Guardar elementos en posiciones numeradas cuando la cantidad puede cambiar.

Declaración
vector<int> v = {1, 2, 3};
Otras declaraciones
vector<int> v; // vacío
vector<int> v(5);    // {0, 0, 0, 0, 0}
vector<int> v(5, 7); // {7, 7, 7, 7, 7}
v.push_back(x)Agrega un elemento al final. O(1) amortizado
Ejemplo
vector<int> v = {1, 2};
v.push_back(3); // v = {1, 2, 3}
cout << v.back(); // imprime 3
v.pop_back()Elimina el último elemento del vector; no devuelve el valor. O(1)
Ejemplo
vector<int> v = {10, 20, 30};
v.pop_back(); // v = {10, 20}
cout << v.back(); // imprime 20

Úsalo solo si hay al menos un elemento.

v.front()Permite leer o modificar el primer elemento. O(1)
Ejemplo
vector<int> v = {10, 20, 30};
v.front() = 99; // v = {99, 20, 30}
cout << v.front(); // imprime 99

Úsalo solo si hay al menos un elemento.

v.back()Permite leer o modificar el último elemento. O(1)
Ejemplo
vector<int> v = {10, 20, 30};
v.back() = 99; // v = {10, 20, 99}
cout << v.back(); // imprime 99

Úsalo solo si hay al menos un elemento.

v[i]Acceso directo por índice, sin verificar límites. O(1)
Ejemplo
vector<int> v = {10, 20, 30};
v[1] = 99; // v = {10, 99, 30}
cout << v[1]; // imprime 99

i debe estar entre 0 y size() - 1.

v.at(i)Accede a la posición i y avisa con una excepción si no existe. O(1)
Ejemplo
vector<int> v = {10, 20, 30};
cout << v.at(1); // imprime 20
v.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
vector<int> v = {1, 2, 3};
cout << v.size(); // imprime 3
v.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
vector<int> v;
cout << boolalpha << v.empty(); // imprime true
v.clear()Borra todos los elementos. O(n)
Ejemplo
vector<int> v = {10, 20, 30};
v.clear(); // v = {}
cout << v.size(); // imprime 0
v.insert(pos, x)Inserta x antes de la posición indicada. O(n)
Ejemplo
vector<int> v = {10, 20, 30};
v.insert(v.begin() + 1, 99); // v = {10, 99, 20, 30}
cout << v[1]; // imprime 99

Después de insertar, vuelve a obtener los iteradores que apuntaban a esa posición o a las siguientes.

v.erase(it) / v.erase(first, last)Borra un elemento o varias posiciones consecutivas. O(n)
Ejemplo
vector<int> v = {10, 20, 30};
v.erase(v.begin() + 1); // v = {10, 30}
for (int x : v) cout << x << ' '; // imprime 10 30

v = {10, 20, 30, 40};
v.erase(v.begin(), v.begin() + 2); // v = {30, 40}
for (int x : v) cout << x << ' '; // imprime 30 40

El rango incluye first, pero no last. Después de borrar, vuelve a obtener los iteradores afectados.

v.resize(n)Cambia el tamaño del vector; si crece, rellena con valores por defecto. O(n)
Ejemplo
vector<int> v = {10, 20, 30};
v.resize(5); // v = {10, 20, 30, 0, 0}
for (int x : v) cout << x << ' '; // imprime 10 20 30 0 0
v.reserve(n)Reserva espacio para n elementos sin agregarlos. O(n)
Ejemplo
vector<int> v;
v.reserve(100); // v sigue vacío; su capacidad es al menos 100
cout << boolalpha << (v.capacity() >= 100); // imprime true
cout << v.size(); // imprime 0

No crea elementos; v[i] sigue requiriendo i < v.size().

v.begin()Devuelve un iterador: una posición que apunta al primer elemento. O(1)
Ejemplo
vector<int> v = {10, 20, 30};
auto it = v.begin();
cout << *it; // imprime 10
v.end()Devuelve el iterador posterior al último elemento. O(1)
Ejemplo
vector<int> v = {10, 20, 30};
auto it = v.end();
--it;
cout << *it; // imprime 30
Recorrer con range-forForma más simple de recorrer todos los elementos. patrón
Ejemplo
vector<int> v = {10, 20, 30};
for (int x : v)
{
    cout << x << ' ';
}
// imprime 10 20 30
Modificar mientras se recorreUsando referencia (&) se puede modificar cada elemento en el mismo contenedor. patrón
Ejemplo
vector<int> v = {1, 2, 3};
for (int &x : v) x *= 2; // v = {2, 4, 6}
for (int x : v) cout << x << ' '; // imprime 2 4 6

Cadena (string)

Guardar, leer y modificar texto.

Declaración
string s = "hola";
s.size() / s.length()Devuelve la longitud del texto. O(1)
Ejemplo
string s = "hola";
cout << s.size();   // imprime 4
cout << s.length(); // imprime 4

En UTF-8, un carácter puede ocupar varios bytes.

s.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
string s;
cout << boolalpha << s.empty(); // imprime true
s.push_back(c)Agrega un carácter al final. O(1) amortizado
Ejemplo
string s = "hola";
s.push_back('!'); // s = "hola!"
cout << s; // imprime hola!
s.pop_back()Elimina el último carácter; no devuelve el valor. O(1)
Ejemplo
string s = "hola!";
s.pop_back(); // s = "hola"
cout << s; // imprime hola

Úsalo solo si hay al menos un elemento.

s.front()Consulta el primer elemento sin eliminarlo. O(1)
Ejemplo
string s = "hola";
cout << s.front(); // imprime h

Úsalo solo si hay al menos un elemento.

s.back()Consulta el último elemento sin eliminarlo. O(1)
Ejemplo
string s = "hola";
cout << s.back(); // imprime a

Úsalo solo si hay al menos un elemento.

s.substr(pos, len)Devuelve una subcadena a partir de pos, con longitud len. O(len)
Ejemplo
string s = "abcdef";
cout << s.substr(2, 3); // imprime cde
s.find(x)Busca una subcadena y devuelve la posición donde empieza, o string::npos si no existe. O(n·m)
Ejemplo
string s = "abcdef";
auto pos = s.find("cd");
cout << pos; // imprime 2

if (s.find("xyz") == string::npos) cout << "No existe";

n = longitud de la cadena, m = longitud buscada; la complejidad indicada es una cota de búsqueda directa.

s.erase(pos, len)Elimina len caracteres a partir de la posición pos. O(n)
Ejemplo
string s = "abcdef";
s.erase(1, 3); // s = "aef"
cout << s; // imprime aef
s.insert(pos, x)Inserta la cadena x en la posición pos. O(n)
Ejemplo
string s = "abcd";
s.insert(2, "XY"); // s = "abXYcd"
cout << s; // imprime abXYcd
s.replace(pos, len, x)Reemplaza len caracteres a partir de pos por la cadena x. O(n)
Ejemplo
string s = "abcdef";
s.replace(1, 3, "XY"); // s = "aXYef"
cout << s; // imprime aXYef
s.clear()Borra todos los elementos. O(n)
Ejemplo
string s = "hola";
s.clear(); // s = ""
cout << s.size(); // imprime 0

Cola doble (deque)

Agregar y quitar elementos rápidamente por ambos extremos.

Declaración
deque<int> dq;

Se usa mucho en ventanas deslizantes, colas monótonas y BFS 0-1.

dq.push_back(x)Agrega un elemento al final. O(1)
Ejemplo
deque<int> dq = {10, 20};
dq.push_back(30); // dq = {10, 20, 30}
cout << dq.back(); // imprime 30
dq.push_front(x)Agrega un elemento al inicio. O(1)
Ejemplo
deque<int> dq = {10, 20};
dq.push_front(5); // dq = {5, 10, 20}
cout << dq.front(); // imprime 5
dq.pop_back()Elimina el elemento del final; no devuelve el valor. O(1)
Ejemplo
deque<int> dq = {10, 20, 30};
dq.pop_back(); // dq = {10, 20}
cout << dq.back(); // imprime 20

Úsalo solo si hay al menos un elemento.

dq.pop_front()Elimina el elemento del inicio; no devuelve el valor. O(1)
Ejemplo
deque<int> dq = {10, 20, 30};
dq.pop_front(); // dq = {20, 30}
cout << dq.front(); // imprime 20

Úsalo solo si hay al menos un elemento.

dq.front()Consulta el primer elemento sin eliminarlo. O(1)
Ejemplo
deque<int> dq = {10, 20, 30};
cout << dq.front(); // imprime 10

Úsalo solo si hay al menos un elemento.

dq.back()Consulta el último elemento sin eliminarlo. O(1)
Ejemplo
deque<int> dq = {10, 20, 30};
cout << dq.back(); // imprime 30

Úsalo solo si hay al menos un elemento.

dq[i]Accede a la posición i, igual que en un vector. O(1)
Ejemplo
deque<int> dq = {10, 20, 30};
dq[1] = 99; // dq = {10, 99, 30}
cout << dq[1]; // imprime 99

i debe estar entre 0 y size() - 1.

dq.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
deque<int> dq = {10, 20, 30};
cout << dq.size(); // imprime 3
dq.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
deque<int> dq;
cout << boolalpha << dq.empty(); // imprime true
dq.clear()Borra todos los elementos. O(n)
Ejemplo
deque<int> dq = {10, 20, 30};
dq.clear(); // dq = {}
cout << dq.size(); // imprime 0

Lista doblemente enlazada (list)

Insertar o borrar rápidamente cuando ya conoces la posición.

Declaración
list<int> l;

No existe l[i]. Para llegar a una posición debes avanzar desde el inicio o el final.

l.push_back(x)Agrega un valor al final. O(1)
Ejemplo
list<int> l = {10, 20};
l.push_back(30); // l = {10, 20, 30}
cout << l.back(); // imprime 30
l.push_front(x)Agrega un valor al inicio. O(1)
Ejemplo
list<int> l = {10, 20};
l.push_front(5); // l = {5, 10, 20}
cout << l.front(); // imprime 5
l.pop_back()Elimina el último elemento; no devuelve su valor. O(1)
Ejemplo
list<int> l = {10, 20, 30};
l.pop_back(); // l = {10, 20}
cout << l.back(); // imprime 20

La lista debe tener al menos un elemento.

l.pop_front()Elimina el primer elemento; no devuelve su valor. O(1)
Ejemplo
list<int> l = {10, 20, 30};
l.pop_front(); // l = {20, 30}
cout << l.front(); // imprime 20

La lista debe tener al menos un elemento.

l.front()Consulta el primer elemento sin eliminarlo. O(1)
Ejemplo
list<int> l = {10, 20, 30};
cout << l.front(); // imprime 10

Úsalo solo si hay al menos un elemento.

l.back()Consulta el último elemento sin eliminarlo. O(1)
Ejemplo
list<int> l = {10, 20, 30};
cout << l.back(); // imprime 30

Úsalo solo si hay al menos un elemento.

l.insert(it, x)Inserta un valor antes de la posición indicada por el iterador. O(1)
Ejemplo
list<int> l = {10, 20, 30};
auto it = next(l.begin());
l.insert(it, 15); // l = {10, 15, 20, 30}
for (int x : l) cout << x << ' '; // imprime 10 15 20 30
l.erase(it)Elimina el elemento señalado por el iterador. O(1)
Ejemplo
list<int> l = {10, 20, 30};
auto it = next(l.begin());
l.erase(it); // l = {10, 30}
for (int x : l) cout << x << ' '; // imprime 10 30

Después de borrarlo, ese iterador ya no es válido.

l.remove(x)Elimina todas las apariciones de un valor específico. O(n)
Ejemplo
list<int> l = {5, 2, 5, 8};
l.remove(5); // l = {2, 8}
for (int x : l) cout << x << ' '; // imprime 2 8
l.reverse()Invierte el orden de todos los elementos. O(n)
Ejemplo
list<int> l = {10, 20, 30};
l.reverse(); // l = {30, 20, 10}
for (int x : l) cout << x << ' '; // imprime 30 20 10
l.sort()Ordena la lista de menor a mayor. O(n log n)
Ejemplo
list<int> l = {30, 10, 20};
l.sort(); // l = {10, 20, 30}
for (int x : l) cout << x << ' '; // imprime 10 20 30

Usa l.sort(); std::sort requiere iteradores de acceso aleatorio.

l.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
list<int> l = {10, 20, 30};
cout << l.size(); // imprime 3
l.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
list<int> l;
cout << boolalpha << l.empty(); // imprime true
l.clear()Borra todos los elementos. O(n)
Ejemplo
list<int> l = {10, 20, 30};
l.clear(); // l = {}
cout << l.size(); // imprime 0

Lista simplemente enlazada (forward list)

Usar una lista ligera que solo se recorre hacia adelante.

Declaración
forward_list<int> l;

Solo avanza hacia adelante y no tiene push_back() ni size(). Se usa poco en programación competitiva.

l.push_front(x)Agrega un elemento al inicio de la lista. O(1)
Ejemplo
forward_list<int> l = {10, 20};
l.push_front(5); // l = {5, 10, 20}
cout << l.front(); // imprime 5
l.pop_front()Elimina el primer elemento; no devuelve el valor. O(1)
Ejemplo
forward_list<int> l = {10, 20, 30};
l.pop_front(); // l = {20, 30}
cout << l.front(); // imprime 20

Úsalo solo si hay al menos un elemento.

l.insert_after(it, x)Inserta un elemento justo después de la posición indicada. O(1)
Ejemplo
forward_list<int> l = {10, 20, 30};
auto it = l.begin();
l.insert_after(it, 15); // l = {10, 15, 20, 30}
for (int x : l) cout << x << ' '; // imprime 10 15 20 30

before_begin() permite operar antes del primer elemento; erase_after(it) requiere que exista un elemento después de it.

l.erase_after(it)Elimina el elemento justo después de la posición indicada. O(1)
Ejemplo
forward_list<int> l = {10, 20, 30};
auto it = l.begin();
l.erase_after(it); // l = {10, 30}
for (int x : l) cout << x << ' '; // imprime 10 30

before_begin() permite operar antes del primer elemento; erase_after(it) requiere que exista un elemento después de it.

l.remove(x)Elimina todas las apariciones de un valor. O(n)
Ejemplo
forward_list<int> l = {5, 2, 5, 8};
l.remove(5); // l = {2, 8}
for (int x : l) cout << x << ' '; // imprime 2 8
l.reverse()Invierte el orden actual de los elementos. O(n)
Ejemplo
forward_list<int> l = {10, 20, 30};
l.reverse(); // l = {30, 20, 10}
for (int x : l) cout << x << ' '; // imprime 30 20 10
l.sort()Ordena los elementos de menor a mayor. O(n log n)
Ejemplo
forward_list<int> l = {30, 10, 20};
l.sort(); // l = {10, 20, 30}
for (int x : l) cout << x << ' '; // imprime 10 20 30
l.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
forward_list<int> l;
cout << boolalpha << l.empty(); // imprime true

Pila (stack)

Sacar primero el último elemento que se agregó.

Declaración
stack<int> st;

Se usa mucho en DFS iterativo, validación de paréntesis y problemas de siguiente elemento mayor.

st.push(x)Agrega un elemento a la cima de la pila. O(1)
Ejemplo
stack<int> st;
st.push(10);
st.push(20); // st = [10, 20], con 20 arriba
cout << st.top(); // imprime 20
st.pop()Elimina el elemento de arriba; no devuelve su valor. O(1)
Ejemplo
stack<int> st;
st.push(10);
st.push(20);
st.pop(); // st = [10], con 10 arriba
cout << st.top(); // imprime 10

Úsalo solo si hay al menos un elemento.

st.top()Consulta el elemento en la cima sin eliminarlo. O(1)
Ejemplo
stack<int> st;
st.push(10);
st.push(20);
cout << st.top(); // imprime 20

Úsalo solo si hay al menos un elemento.

st.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
stack<int> st;
st.push(10);
st.push(20);
cout << st.size(); // imprime 2
st.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
stack<int> st;
cout << boolalpha << st.empty(); // imprime true

Cola (queue)

Sacar primero el primer elemento que se agregó.

Declaración
queue<int> q;

Se usa mucho en BFS y en el algoritmo de Kahn para orden topológico.

q.push(x)Agrega un elemento al final de la cola. O(1)
Ejemplo
queue<int> q;
q.push(10);
q.push(20); // q = [10, 20], con 10 al frente
cout << q.back(); // imprime 20
q.pop()Elimina el elemento del frente; no devuelve su valor. O(1)
Ejemplo
queue<int> q;
q.push(10);
q.push(20);
q.pop(); // q = [20], con 20 al frente
cout << q.front(); // imprime 20

Úsalo solo si hay al menos un elemento.

q.front()Consulta el elemento del frente sin eliminarlo. O(1)
Ejemplo
queue<int> q;
q.push(10);
q.push(20);
cout << q.front(); // imprime 10

Úsalo solo si hay al menos un elemento.

q.back()Consulta el último elemento agregado. O(1)
Ejemplo
queue<int> q;
q.push(10);
q.push(20);
cout << q.back(); // imprime 20

Úsalo solo si hay al menos un elemento.

q.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
queue<int> q;
q.push(10);
q.push(20);
cout << q.size(); // imprime 2
q.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
queue<int> q;
cout << boolalpha << q.empty(); // imprime true

Cola de prioridad

Mantener disponible el valor mayor o menor sin ordenar todo manualmente.

Declaración
priority_queue<int> pq; // el mayor queda arriba
Otras declaraciones
priority_queue<int, vector<int>, greater<int>> pq; // el menor queda arriba

top() consulta el elemento con mayor prioridad y pop() lo elimina.

pq.push(x)Agrega un elemento y conserva el de mayor prioridad arriba. O(log n)
Ejemplo
priority_queue<int> pq;
pq.push(10);
pq.push(50);
pq.push(20); // pq contiene {10, 20, 50}; 50 queda arriba
cout << pq.top(); // imprime 50
pq.pop()Elimina el elemento de mayor prioridad actual; no devuelve el valor. O(log n)
Ejemplo
priority_queue<int> pq;
pq.push(10);
pq.push(50);
pq.push(20);
pq.pop(); // elimina 50; 20 queda arriba
cout << pq.top(); // imprime 20

Úsalo solo si hay al menos un elemento.

pq.top()Consulta el elemento de mayor prioridad sin quitarlo. O(1)
Ejemplo
priority_queue<int> pq;
pq.push(10);
pq.push(50);
pq.push(20);
cout << pq.top(); // imprime 50

Úsalo solo si hay al menos un elemento.

pq.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
priority_queue<int> pq;
pq.push(10);
pq.push(20);
cout << pq.size(); // imprime 2
pq.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
priority_queue<int> pq;
cout << boolalpha << pq.empty(); // imprime true

Par (pair)

Agrupar dos valores relacionados en una sola variable.

Declaración
pair<int, int> p = {5, 10};
p.firstAccede al primer valor almacenado. O(1)
Ejemplo
pair<int, int> p = {5, 10};
cout << p.first; // imprime 5
p.secondAccede al segundo valor almacenado. O(1)
Ejemplo
pair<int, int> p = {5, 10};
cout << p.second; // imprime 10
Lista de adyacencia con pesosUn par {vecino, peso} permite guardar una conexión con su costo. patrón
Ejemplo
int n = 3;
vector<vector<pair<int, int>>> graph(n);
graph[0].push_back({1, 7}); // nodo 1, peso 7
cout << graph[0][0].second; // imprime 7

Tupla (tuple)

Agrupar tres o más valores en una sola variable.

Declaración
tuple<int, int, string> t = {10, 20, "hola"};
get<i>(t)Accede al elemento en la posición i (empezando desde 0). O(1)
Ejemplo
tuple<int, int, string> t = {10, 20, "hola"};
cout << get<0>(t); // imprime 10
cout << get<2>(t); // imprime hola

i debe ser una constante en compilación; en este ejemplo, 0, 1 o 2.

Desempaquetar con structured bindingauto [a, b, c] separa los valores en variables individuales. También funciona con pair. patrón
Ejemplo
tuple<int, int, string> t = {10, 20, "hola"};
auto [a, b, texto] = t;
cout << a << ' ' << texto; // imprime 10 hola

Set

Guardar valores sin repetirlos y mantenerlos ordenados.

Declaración
set<int> s;

s.insert(5);
s.insert(2);
s.insert(10);
s.insert(5);
// contenido: 2 5 10
s.insert(x)Agrega x solo si todavía no existe. O(log n)
Ejemplo
set<int> s = {2, 5};
s.insert(10); // s = {2, 5, 10}
cout << s.count(10); // imprime 1
s.erase(x)Elimina el elemento con ese valor si existe. O(log n)
Ejemplo
set<int> s = {2, 5, 10};
s.erase(5); // s = {2, 10}
cout << s.count(5); // imprime 0
s.find(x)Devuelve un iterador al elemento, o a end() si no existe. O(log n)
Ejemplo
set<int> s = {2, 5, 10};
auto it = s.find(5);
if (it != s.end()) cout << *it; // imprime 5
s.count(x)Devuelve 1 si x existe y 0 si no existe. O(log n)
Ejemplo
set<int> s = {2, 5, 10};
cout << s.count(5); // imprime 1
cout << s.count(7); // imprime 0
s.lower_bound(x)Devuelve un iterador al primer elemento mayor o igual que x. O(log n)
Ejemplo
set<int> s = {2, 5, 8, 10};
auto it = s.lower_bound(6);
cout << *it; // imprime 8
s.upper_bound(x)Devuelve un iterador al primer elemento estrictamente mayor que x. O(log n)
Ejemplo
set<int> s = {2, 5, 8, 10};
auto it = s.upper_bound(5);
cout << *it; // imprime 8
s.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
set<int> s = {10, 20, 30};
cout << s.size(); // imprime 3
s.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
set<int> s;
cout << boolalpha << s.empty(); // imprime true
s.clear()Borra todos los elementos. O(n)
Ejemplo
set<int> s = {10, 20, 30};
s.clear(); // s = {}
cout << s.size(); // imprime 0

Unordered set

Guardar valores sin repetirlos cuando no importa el orden.

Declaración
unordered_set<int> s;

No mantiene los valores ordenados. Sus operaciones suelen ser O(1), aunque en el peor caso pueden tardar O(n).

s.insert(x)Agrega un elemento si no existía ya. O(1) promedio
Ejemplo
unordered_set<int> s = {2, 5};
s.insert(10); // s contiene {2, 5, 10}, sin orden fijo
cout << s.count(10); // imprime 1
s.erase(x)Elimina el elemento con ese valor. O(1) promedio
Ejemplo
unordered_set<int> s = {2, 5, 10};
s.erase(5); // s contiene {2, 10}
cout << s.count(5); // imprime 0
s.find(x)Devuelve un iterador al elemento, o end() si no existe. O(1) promedio
Ejemplo
unordered_set<int> s = {2, 5, 10};
auto it = s.find(5);
if (it != s.end()) cout << *it; // imprime 5
s.count(x)Devuelve 1 si existe, 0 si no. O(1) promedio
Ejemplo
unordered_set<int> s = {2, 5, 10};
cout << s.count(5); // imprime 1
cout << s.count(7); // imprime 0
s.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
unordered_set<int> s = {10, 20, 30};
cout << s.size(); // imprime 3
s.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
unordered_set<int> s;
cout << boolalpha << s.empty(); // imprime true
s.clear()Borra todos los elementos. O(n)
Ejemplo
unordered_set<int> s = {10, 20, 30};
s.clear(); // s = {}
cout << s.size(); // imprime 0

Multiset

Guardar valores repetidos y mantenerlos ordenados.

Declaración
multiset<int> ms;

ms.insert(5);
ms.insert(5);
ms.insert(5);
// contenido: 5 5 5

n = elementos almacenados; k = coincidencias de la clave.

ms.insert(x)Agrega un elemento, incluso si ya hay copias de él. O(log n)
Ejemplo
multiset<int> ms = {2, 5, 5};
ms.insert(5); // ms = {2, 5, 5, 5}
cout << ms.count(5); // imprime 3
ms.find(x)Devuelve un iterador a una de las copias del elemento. O(log n)
Ejemplo
multiset<int> ms = {2, 5, 5, 8};
auto it = ms.find(5);
if (it != ms.end()) cout << *it; // imprime 5
ms.count(x)Cuenta cuántas copias del elemento existen. O(log n + k)
Ejemplo
multiset<int> ms = {2, 5, 5, 8};
cout << ms.count(5); // imprime 2

k = número de copias de x.

ms.lower_bound(x)Devuelve un iterador al primer elemento mayor o igual al valor buscado. O(log n)
Ejemplo
multiset<int> ms = {3, 5, 5, 8};
auto it = ms.lower_bound(4);
cout << *it; // imprime 5

Si no hay un resultado, devuelve end(). Compruébalo antes de leer el iterador.

ms.upper_bound(x)Devuelve un iterador al primer elemento estrictamente mayor al valor buscado. O(log n)
Ejemplo
multiset<int> ms = {3, 5, 5, 8};
auto it = ms.upper_bound(5);
cout << *it; // imprime 8

Si no hay un resultado, devuelve end(). Compruébalo antes de leer el iterador.

ms.erase(x)Borra todas las copias de x. O(log n + k)
Ejemplo
multiset<int> ms = {2, 5, 5, 8};
ms.erase(5); // ms = {2, 8}
cout << ms.count(5); // imprime 0

k = número de copias borradas; usa erase(it) para borrar solo una.

ms.erase(it)Borra una sola copia. O(1) amortizado
Ejemplo
multiset<int> ms = {2, 5, 5, 8};
auto it = ms.find(5);
ms.erase(it); // ms = {2, 5, 8}; borra una sola copia
cout << ms.count(5); // imprime 1

Con un iterador ya obtenido; buscarlo con find() cuesta O(log n).

Unordered multiset

Guardar valores repetidos cuando no importa el orden.

Declaración
unordered_multiset<int> s;

Acepta valores repetidos y no los mantiene ordenados. Sus operaciones suelen ser O(1).

s.insert(x)Agrega un elemento, incluso si ya hay copias iguales. O(1) promedio
Ejemplo
unordered_multiset<int> s = {2, 5, 5};
s.insert(5); // s contiene tres copias de 5
cout << s.count(5); // imprime 3
s.erase(x)Elimina todas las copias de ese valor. O(1 + k) promedio
Ejemplo
unordered_multiset<int> s = {2, 5, 5};
s.erase(5); // s contiene solo {2}
cout << s.count(5); // imprime 0
s.find(x)Devuelve un iterador a una copia del valor. O(1) promedio
Ejemplo
unordered_multiset<int> s = {2, 5, 5};
auto it = s.find(5);
if (it != s.end()) cout << *it; // imprime 5
s.count(x)Cuenta cuántas copias existen de ese valor. O(1 + k) promedio
Ejemplo
unordered_multiset<int> s = {2, 5, 5, 8};
cout << s.count(5); // imprime 2

Map

Relacionar cada clave con un valor y mantener las claves ordenadas.

Declaración
map<string, int> mp;

mp["Juan"] = 10;
mp["Pedro"] = 20;
mp[key]Accede al valor de key; si no existe, crea la clave con un valor inicial. O(log n)
Ejemplo
map<string, int> mp;
mp["Ana"] = 10;
mp["Ana"]++; // mp["Ana"] = 11
cout << mp["Ana"]; // imprime 11
mp.at(key)Accede al valor de una clave con verificación; lanza excepción si no existe. O(log n)
Ejemplo
map<string, int> mp = {{"Ana", 10}};
cout << mp.at("Ana"); // imprime 10
mp.insert({key, value})Inserta un par clave-valor sólo si la clave no existe todavía. O(log n)
Ejemplo
map<string, int> mp = {{"Ana", 10}};
mp.insert({"Luis", 20}); // mp = {{"Ana", 10}, {"Luis", 20}}
cout << mp["Luis"]; // imprime 20
mp.erase(key)Elimina la entrada asociada a esa clave. O(log n)
Ejemplo
map<string, int> mp = {{"Ana", 10}, {"Luis", 20}};
mp.erase("Ana"); // mp = {{"Luis", 20}}
cout << mp.count("Ana"); // imprime 0
mp.find(key)Devuelve un iterador a la entrada, o end() si la clave no existe. O(log n)
Ejemplo
map<string, int> mp = {{"Ana", 10}, {"Luis", 20}};
auto it = mp.find("Luis");
if (it != mp.end()) cout << it->second; // imprime 20
mp.count(key)Devuelve 1 si la clave existe, 0 si no. O(log n)
Ejemplo
map<string, int> mp = {{"Ana", 10}};
cout << mp.count("Ana");  // imprime 1
cout << mp.count("Pedro"); // imprime 0
mp.lower_bound(key)Devuelve un iterador al primer par cuya clave sea mayor o igual al valor buscado. O(log n)
Ejemplo
map<int, string> mp = {{2, "dos"}, {5, "cinco"}, {8, "ocho"}};
auto it = mp.lower_bound(6);
cout << it->first; // imprime 8

Si no hay un resultado, devuelve end(). Compruébalo antes de leer el iterador.

mp.upper_bound(key)Devuelve un iterador al primer par cuya clave sea estrictamente mayor al valor buscado. O(log n)
Ejemplo
map<int, string> mp = {{2, "dos"}, {5, "cinco"}, {8, "ocho"}};
auto it = mp.upper_bound(5);
cout << it->first; // imprime 8

Si no hay un resultado, devuelve end(). Compruébalo antes de leer el iterador.

mp.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
map<string, int> mp = {{"Ana", 10}, {"Luis", 20}};
cout << mp.size(); // imprime 2
mp.empty()Devuelve true si no hay elementos. O(1)
Ejemplo
map<string, int> mp;
cout << boolalpha << mp.empty(); // imprime true
mp.clear()Borra todos los elementos. O(n)
Ejemplo
map<string, int> mp = {{"Ana", 10}, {"Luis", 20}};
mp.clear(); // mp = {}
cout << mp.size(); // imprime 0
Recorrer con structured bindingauto [key, value] separa cada entrada en su clave y su valor. patrón
Ejemplo
map<string, int> mp = {{"Ana", 10}, {"Luis", 20}};
for (auto [nombre, puntos] : mp)
{
    cout << nombre << ": " << puntos << '\n';
}
// imprime Ana: 10 y Luis: 20

Unordered map

Relacionar claves con valores cuando no importa el orden.

Declaración
unordered_map<int, int> mp;

No mantiene las claves ordenadas. Sus operaciones suelen ser O(1), aunque en el peor caso pueden tardar O(n).

mp[key]Accede (o crea) el valor asociado a una clave. O(1) promedio
Ejemplo
unordered_map<int, int> frecuencia;
frecuencia[5]++;
frecuencia[5]++; // frecuencia[5] = 2
cout << frecuencia[5]; // imprime 2
mp.insert({key, value})Agrega un par clave-valor si la clave todavía no existe. No reemplaza un valor ya guardado. O(1) promedio
Ejemplo
unordered_map<int, string> mp = {{1, "uno"}};
mp.insert({2, "dos"}); // mp contiene {1: "uno", 2: "dos"}
cout << mp[2]; // imprime dos
mp.erase(key)Elimina la entrada con esa clave. Si no existe, no elimina nada. O(1) promedio
Ejemplo
unordered_map<int, string> mp = {{1, "uno"}, {2, "dos"}};
mp.erase(1); // mp contiene solo {2: "dos"}
cout << mp.count(1); // imprime 0
mp.find(key)Busca una clave y devuelve un iterador a su entrada; devuelve end() si no existe. O(1) promedio
Ejemplo
unordered_map<int, string> mp = {{1, "uno"}, {2, "dos"}};
auto it = mp.find(2);
if (it != mp.end()) cout << it->second; // imprime dos
mp.count(key)Devuelve 1 si la clave existe o 0 si no existe; aquí no se repiten claves. O(1) promedio
Ejemplo
unordered_map<int, string> mp = {{1, "uno"}};
cout << mp.count(1); // imprime 1
cout << mp.count(2); // imprime 0
Contar frecuenciasCuenta cuántas veces aparece cada valor. patrón
Ejemplo
vector<int> v = {1, 2, 2, 3, 3, 3};
unordered_map<int, int> frecuencia;

for (int x : v) frecuencia[x]++;
// frecuencia = {1: 1, 2: 2, 3: 3}

cout << frecuencia[1] << ' '; // imprime 1
cout << frecuencia[2] << ' '; // imprime 2
cout << frecuencia[3];        // imprime 3

Multimap

Guardar varios valores por cada clave y mantener las claves ordenadas.

Declaración
multimap<int, string> mp;

mp.insert({1, "A"});
mp.insert({1, "B"});
mp.insert({1, "C"});

A diferencia de map, permite claves repetidas y no usa mp[key].

mp.insert({key, value})Inserta una nueva entrada, incluso si ya existen otras con la misma clave. O(log n)
Ejemplo
multimap<int, string> mp = {{1, "A"}, {1, "B"}};
mp.insert({1, "C"}); // la clave 1 queda asociada con A, B y C
cout << mp.count(1); // imprime 3
mp.find(key)Devuelve un iterador a una de las entradas con esa clave. O(log n)
Ejemplo
multimap<int, string> mp = {{1, "A"}, {1, "B"}};
auto it = mp.find(1);
if (it != mp.end()) cout << it->first; // imprime 1
mp.erase(key)Elimina todas las entradas asociadas a esa clave. O(log n + k)
Ejemplo
multimap<int, string> mp = {{1, "A"}, {1, "B"}, {2, "C"}};
mp.erase(1); // mp contiene solo {2: "C"}
cout << mp.count(1); // imprime 0
mp.count(key)Cuenta cuántas entradas existen con esa clave. O(log n + k)
Ejemplo
multimap<int, string> mp = {{1, "A"}, {1, "B"}, {2, "C"}};
cout << mp.count(1); // imprime 2
mp.lower_bound(key)Devuelve un iterador al primer par cuya clave sea mayor o igual al valor buscado. O(log n)
Ejemplo
multimap<int, string> mp = {{1, "A"}, {1, "B"}, {3, "C"}};
auto it = mp.lower_bound(2);
cout << it->first; // imprime 3

Si no hay un resultado, devuelve end(). Compruébalo antes de leer el iterador.

mp.upper_bound(key)Devuelve un iterador al primer par cuya clave sea estrictamente mayor al valor buscado. O(log n)
Ejemplo
multimap<int, string> mp = {{1, "A"}, {1, "B"}, {3, "C"}};
auto it = mp.upper_bound(1);
cout << it->first; // imprime 3

Si no hay un resultado, devuelve end(). Compruébalo antes de leer el iterador.

mp.equal_range(key)Devuelve desde la primera hasta después de la última entrada con esa clave. O(log n)
Ejemplo
multimap<int, string> mp = {{1, "A"}, {1, "B"}, {2, "C"}};
auto [first, last] = mp.equal_range(1);
for (auto it = first; it != last; ++it) cout << it->second << ' ';
// imprime A B

Unordered multimap

Guardar varios valores por clave cuando no importa el orden.

Declaración
unordered_multimap<int, string> mp;

Permite claves repetidas y no las mantiene ordenadas. Sus operaciones suelen ser O(1).

mp.insert({key, value})Inserta una entrada, incluso si ya existen otras con la misma clave. O(1) promedio
Ejemplo
unordered_multimap<int, string> mp = {{1, "A"}};
mp.insert({1, "B"}); // la clave 1 queda asociada con A y B
cout << mp.count(1); // imprime 2
mp.find(key)Devuelve un iterador a una de las entradas con esa clave. O(1) promedio
Ejemplo
unordered_multimap<int, string> mp = {{1, "A"}, {2, "B"}};
auto it = mp.find(2);
if (it != mp.end()) cout << it->second; // imprime B
mp.count(key)Cuenta cuántas entradas existen con esa clave. O(1 + k) promedio
Ejemplo
unordered_multimap<int, string> mp = {{1, "A"}, {1, "B"}, {2, "C"}};
cout << mp.count(1); // imprime 2
mp.erase(key)Elimina todas las entradas asociadas a esa clave. O(1 + k) promedio
Ejemplo
unordered_multimap<int, string> mp = {{1, "A"}, {1, "B"}, {2, "C"}};
mp.erase(1); // mp contiene solo {2: "C"}
cout << mp.count(1); // imprime 0
mp.equal_range(key)Devuelve todas las entradas que tienen esa clave. O(1 + k) promedio
Ejemplo
unordered_multimap<int, string> mp = {{1, "A"}, {1, "B"}, {2, "C"}};
auto [first, last] = mp.equal_range(1);
for (auto it = first; it != last; ++it) cout << it->second << ' ';
// imprime A y B, en cualquier orden

Bitset

Guardar una cantidad fija de valores que solo pueden ser 0 o 1.

Declaración
bitset<8> bits("10101010");
Otras declaraciones
bitset<8> bits; // 00000000

El tamaño se fija al declarar bitset<N>; la posición 0 es el bit de la derecha.

bits.set(i)Pone el bit en la posición i en 1. O(1)
Ejemplo
bitset<4> bits("0000");
bits.set(3); // bits = 1000
cout << bits; // imprime 1000
bits.reset(i)Pone el bit en la posición i en 0. O(1)
Ejemplo
bitset<4> bits("1010");
bits.reset(1); // bits = 1000
cout << bits; // imprime 1000
bits.flip(i)Invierte el bit en la posición i (0→1 o 1→0). O(1)
Ejemplo
bitset<4> bits("1010");
bits.flip(0); // bits = 1011
cout << bits; // imprime 1011
bits.test(i)Consulta el valor del bit en la posición i. O(1)
Ejemplo
bitset<4> bits("1010");
cout << boolalpha << bits.test(3); // imprime true
bits.count()Cuenta cuántos bits están en 1. Depende de la implementación
Ejemplo
bitset<6> bits("101101");
cout << bits.count(); // imprime 4
bits.any()Devuelve true si al menos un bit es 1. Depende de la implementación
Ejemplo
bitset<4> bits("0101");
cout << boolalpha << bits.any(); // imprime true
bits.none()Devuelve true si todos los bits son 0. Depende de la implementación
Ejemplo
bitset<4> bits("0101");
cout << boolalpha << bits.none(); // imprime false
bits.all()Devuelve true si todos los bits son 1. Depende de la implementación
Ejemplo
bitset<4> bits("0101");
cout << boolalpha << bits.all(); // imprime false
bits.size()Devuelve cuántos elementos hay. O(1)
Ejemplo
bitset<8> bits;
cout << bits.size(); // imprime 8
bits[i]Acceso directo (lectura o escritura) al bit en la posición i. O(1)
Ejemplo
bitset<4> bits("0000");
bits[1] = 1; // bits = 0010
cout << bits; // imprime 0010

i debe estar entre 0 y size() - 1.

operator&Conserva un 1 únicamente donde ambos operandos tienen 1. Depende de la implementación
Ejemplo
bitset<4> a("0101");
bitset<4> b("0011");
cout << (a & b); // imprime 0001
operator|Coloca un 1 donde al menos uno de los operandos tiene 1. Depende de la implementación
Ejemplo
bitset<4> a("0101");
bitset<4> b("0011");
cout << (a | b); // imprime 0111
operator^Coloca un 1 donde los bits de los operandos son distintos. Depende de la implementación
Ejemplo
bitset<4> a("0101");
bitset<4> b("0011");
cout << (a ^ b); // imprime 0110
operator~Invierte cada bit: 0 pasa a 1 y 1 pasa a 0. Depende de la implementación
Ejemplo
bitset<4> a("0101");
cout << (~a); // imprime 1010
operator<<Desplaza los bits a la izquierda y rellena con ceros. Depende de la implementación
Ejemplo
bitset<4> a("0101");
cout << (a << 1); // imprime 1010
operator>>Desplaza los bits a la derecha y rellena con ceros. Depende de la implementación
Ejemplo
bitset<4> a("0101");
cout << (a >> 1); // imprime 0010

Lista de adyacencia

Guardar, para cada nodo, la lista de nodos conectados directamente.

Declaración
int n = 8;
vector<vector<int>> graph(n);

Los nodos se numeran de 0 a n - 1. Es la representación más común cuando hay pocas conexiones.

Agregar arista dirigidaGuarda una conexión que va de u hacia v. O(1) amortizado
Ejemplo
int n = 4;
vector<vector<int>> graph(n);
int u = 0, v = 2;
graph[u].push_back(v); // graph[0] = {2}
cout << graph[0][0]; // imprime 2
Agregar arista no dirigidaGuarda u → v y también v → u. O(1) amortizado
Ejemplo
int n = 4;
vector<vector<int>> graph(n);
int u = 0, v = 2;
graph[u].push_back(v);
graph[v].push_back(u); // graph[0] = {2} y graph[2] = {0}
cout << graph[0][0] << ' ' << graph[2][0]; // imprime 2 0
Recorrer vecinos de un nodoVisita todos los nodos conectados directamente con u. O(grado(u))
Ejemplo
vector<vector<int>> graph = {{1, 2}, {0}, {0}};
int u = 0;
for (int v : graph[u]) cout << v << ' '; // imprime 1 2

Grafo con pesos

Guardar cada conexión junto con su costo, distancia o peso.

Declaración
int n = 8;
vector<vector<pair<int, int>>> graph(n); // cada par es {vecino, peso}

Los nodos se numeran de 0 a n - 1. Cada par guarda {vecino, peso}.

Agregar arista dirigida con pesoGuarda una conexión de u hacia v junto con su peso. O(1) amortizado
Ejemplo
int n = 4;
vector<vector<pair<int, int>>> graph(n);
int u = 0, v = 2, peso = 7;
graph[u].push_back({v, peso}); // graph[0] = {{2, 7}}
cout << graph[0][0].second; // imprime 7
Agregar arista no dirigida con pesoGuarda la conexión y su peso en ambos sentidos. O(1) amortizado
Ejemplo
int n = 4;
vector<vector<pair<int, int>>> graph(n);
int u = 0, v = 2, peso = 7;
graph[u].push_back({v, peso});
graph[v].push_back({u, peso}); // 0 y 2 quedan conectados con peso 7
cout << graph[2][0].first; // imprime 0
Recorrer vecinos con pesoVisita cada vecino de u junto con el peso de la conexión. O(grado(u))
Ejemplo
vector<vector<pair<int, int>>> graph(3);
graph[0] = {{1, 5}, {2, 8}};

for (auto [v, peso] : graph[0])
    cout << v << ':' << peso << ' ';
// imprime 1:5 2:8

Matriz de adyacencia

Usar una tabla para consultar directamente si dos nodos están conectados.

Declaración
int n = 8;
vector<vector<int>> graph(n, vector<int>(n));

Usa memoria O(V²), por lo que conviene para grafos pequeños o con muchas conexiones. En un grafo no dirigido, guarda también graph[v][u].

Agregar aristaGuarda 1 en graph[u][v] para marcar la conexión. O(1)
Ejemplo
int n = 4;
vector<vector<int>> graph(n, vector<int>(n));
int u = 0, v = 2;
graph[u][v] = 1; // graph[0][2] = 1: sí existe la arista
cout << graph[0][2]; // imprime 1
Agregar arista con pesoGuarda el peso en graph[u][v]. O(1)
Ejemplo
int n = 4;
vector<vector<int>> graph(n, vector<int>(n));
int u = 0, v = 2, peso = 7;
graph[u][v] = peso; // graph[0][2] = 7
cout << graph[0][2]; // imprime 7

Estructuras de datos avanzadas

Árbol binario

Modelar una jerarquía donde cada nodo tiene como máximo dos hijos.

Implementación
struct Node
{
    int value;
    Node* left;
    Node* right;

    Node(int value)
    {
        this->value = value;
        left = nullptr;
        right = nullptr;
    }
};
Uso / inicialización
Node root(5);
Node left(3), right(8);
root.left = &left;
root.right = &right;

Cada nodo guarda un valor y enlaces a sus hijos izquierdo y derecho. Conéctalos según el problema; esta base no ordena ni balancea el árbol.

Union-Find (DSU)

Mantener grupos separados, unirlos y comprobar si dos elementos están conectados.

Implementación
struct DSU
{
    vector<int> parent;
    vector<int> size;

    DSU(int n)
    {
        assert(n >= 0);
        parent.resize(n);
        size.assign(n, 1);

        for (int i = 0; i < n; i++)
        {
            parent[i] = i;
        }
    }

    int find(int x)
    {
        assert(x >= 0 && x < int(parent.size()));
        if (parent[x] == x)
        {
            return x;
        }

        return parent[x] = find(parent[x]);
    }

    bool unite(int a, int b)
    {
        a = find(a);
        b = find(b);

        if (a == b)
        {
            return false;
        }

        if (size[a] < size[b])
        {
            swap(a, b);
        }

        parent[b] = a;
        size[a] += size[b];

        return true;
    }
};
Uso / inicialización
int n = 8;
DSU dsu(n);

Úsalo en conectividad dinámica y Kruskal cuando solo agregas uniones. Índices [0, n); memoria O(n).

dsu.find(x)Devuelve el representante del grupo de x. O(α(n)) amortizado
Ejemplo
DSU dsu(5);
dsu.unite(1, 2);
cout << boolalpha << (dsu.find(1) == dsu.find(2));
// imprime true
dsu.unite(a, b)Une los grupos de a y b; devuelve false si ya estaban conectados. O(α(n)) amortizado
Ejemplo
DSU dsu(5);
bool primera_union = dsu.unite(1, 2); // grupos: {0}, {1, 2}, {3}, {4}
cout << boolalpha << primera_union; // imprime true
bool segunda_union = dsu.unite(1, 2); // los grupos no cambian
cout << segunda_union;                       // imprime false

Árbol de Fenwick (BIT)

Mantener sumas de prefijo mientras cambian valores individuales.

Implementación
struct Fenwick
{
    int n;
    vector<long long> bit;

    Fenwick(int n)
    {
        assert(n >= 0);
        this->n = n;
        bit.assign(n + 1, 0);
    }

    void add(int i, long long x)
    {
        assert(i >= 1 && i <= n);
        for (; i <= n; i += i & -i)
        {
            bit[i] += x;
        }
    }

    long long sum(int i)
    {
        assert(i >= 0 && i <= n);
        long long ans = 0;

        for (; i > 0; i -= i & -i)
        {
            ans += bit[i];
        }

        return ans;
    }

    long long query(int l, int r)
    {
        assert(l >= 1 && l <= r && r <= n);
        return sum(r) - sum(l - 1);
    }
};
Uso / inicialización
int n = 8;
Fenwick ft(n);

Es una opción compacta para sumas y actualizaciones puntuales. Usa índices [1, n]; add(i, x) suma x, no lo asigna.

ft.add(i, x)Suma x al valor de la posición i. O(log n)
Ejemplo
Fenwick ft(5);
ft.add(3, 5); // valor[3] = 5
ft.add(3, 2); // valor[3] = 7
cout << ft.query(3, 3); // imprime 7
ft.sum(i)Devuelve la suma de prefijo desde 1 hasta i. O(log n)
Ejemplo
Fenwick ft(5);
ft.add(1, 4);
ft.add(3, 5);
ft.add(5, 2);
cout << ft.sum(3); // imprime 9
ft.query(l, r)Devuelve la suma del rango [l, r], calculada como sum(r) - sum(l-1). O(log n)
Ejemplo
Fenwick ft(5);
ft.add(1, 4);
ft.add(2, 3);
ft.add(4, 7);
cout << ft.query(2, 4); // imprime 10

Árbol de segmentos

Consultar rangos mientras se actualizan valores del arreglo.

Implementación
struct SegmentTree {
    int n;
    vector<long long> tree;

    explicit SegmentTree(const vector<long long>& a) { build(a); }

    void build(const vector<long long>& a) {
        n = int(a.size());
        tree.assign(4 * n, 0);
        if (n) build_node(a, 1, 0, n - 1);
    }

    void update(int pos, long long value) {
        assert(0 <= pos && pos < n);
        update_node(1, 0, n - 1, pos, value);
    }

    long long query(int l, int r) const {
        assert(0 <= l && l <= r && r < n);
        return query_node(1, 0, n - 1, l, r);
    }

private:
    void build_node(const vector<long long>& a, int node, int l, int r) {
        if (l == r) { tree[node] = a[l]; return; }
        int mid = l + (r - l) / 2;
        build_node(a, node * 2, l, mid);
        build_node(a, node * 2 + 1, mid + 1, r);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    void update_node(int node, int l, int r, int pos, long long value) {
        if (l == r) { tree[node] = value; return; }
        int mid = l + (r - l) / 2;
        if (pos <= mid) update_node(node * 2, l, mid, pos, value);
        else update_node(node * 2 + 1, mid + 1, r, pos, value);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long long query_node(int node, int l, int r, int ql, int qr) const {
        if (qr < l || r < ql) return 0; // neutro de la suma
        if (ql <= l && r <= qr) return tree[node];
        int mid = l + (r - l) / 2;
        return query_node(node * 2, l, mid, ql, qr)
             + query_node(node * 2 + 1, mid + 1, r, ql, qr);
    }
};
Uso / inicialización
vector<long long> a = {2, 4, 6};
SegmentTree st(a);

Esta versión suma rangos [l, r] y asigna valores por posición. Usa índices [0, n) y memoria O(n).

Para consultar mínimos o máximos, cambia la combinación y su valor neutro.

st.build(a)Construye o reconstruye a partir del arreglo. O(n)
Ejemplo
vector<long long> a = {1, 2, 3};
SegmentTree st(a);

vector<long long> b = {4, 5, 6};
st.build(b); // el árbol ahora representa {4, 5, 6}
cout << st.query(0, 2); // imprime 15
st.update(pos, value)Asigna un valor en una posición. O(log n)
Ejemplo
vector<long long> a = {2, 4, 6};
SegmentTree st(a);
st.update(1, 10); // arreglo representado = {2, 10, 6}
cout << st.query(0, 2); // imprime 18
st.query(l, r)Devuelve la suma del rango inclusivo. O(log n)
Ejemplo
vector<long long> a = {2, 4, 6, 8};
SegmentTree st(a);
cout << st.query(1, 3); // imprime 18

Tabla dispersa (Sparse Table)

Precalcular mínimos de rangos en un arreglo que no cambia.

Implementación
struct SparseTable {
    vector<vector<int>> table;
    vector<int> lg;

    explicit SparseTable(const vector<int>& a) { build(a); }

    void build(const vector<int>& a) {
        int n = int(a.size());
        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
        table.clear();
        if (n == 0) return;
        table.assign(lg[n] + 1, vector<int>(n));
        table[0] = a;
        for (int k = 1; k <= lg[n]; ++k)
            for (int i = 0; i + (1 << k) <= n; ++i)
                table[k][i] = min(table[k - 1][i],
                                  table[k - 1][i + (1 << (k - 1))]);
    }

    int query(int l, int r) const {
        assert(l >= 0 && l <= r && r + 1 < int(lg.size()));
        int k = lg[r - l + 1];
        return min(table[k][l], table[k][r - (1 << k) + 1]);
    }
};
Uso / inicialización
vector<int> a = {7, 2, 5, 1};
SparseTable st(a);

Conviene cuando habrá muchas consultas y ninguna actualización. Usa rangos [l, r] inclusivos y memoria O(n log n).

La consulta O(1) también se adapta a máximo o GCD; esta forma no sirve para sumas.

st.build(a)Precalcula mínimos; también permite reconstruir. O(n log n)
Ejemplo
vector<int> a = {7, 2, 5, 1};
SparseTable st(a);

vector<int> b = {9, 4, 6};
st.build(b); // la tabla ahora representa {9, 4, 6}
cout << st.query(0, 2); // imprime 4
st.query(l, r)Devuelve el mínimo del rango inclusivo. O(1)
Ejemplo
vector<int> a = {7, 2, 5, 1};
SparseTable st(a);
cout << st.query(1, 3); // imprime 1

Trie

Guardar muchas palabras y recorrer sus prefijos carácter por carácter.

Implementación
struct Trie {
    struct Node {
        array<int, 26> child;
        bool end = false;
        Node() { child.fill(-1); }
    };
    vector<Node> nodes = vector<Node>(1);

    void insert(const string& s) {
        int u = 0;
        for (char c : s) {
            assert(c >= 'a' && c <= 'z');
            int i = c - 'a';
            if (nodes[u].child[i] == -1) {
                int next = int(nodes.size());
                nodes[u].child[i] = next;
                nodes.emplace_back();
            }
            u = nodes[u].child[i];
        }
        nodes[u].end = true;
    }

    bool search(const string& s) const {
        int u = 0;
        for (char c : s) {
            assert(c >= 'a' && c <= 'z');
            int next = nodes[u].child[c - 'a'];
            if (next == -1) return false;
            u = next;
        }
        return nodes[u].end;
    }
};
Uso / inicialización
Trie trie;

Cada camino representa un prefijo compartido. Esta versión acepta letras a–z y search() comprueba palabras completas.

trie.insert(s)Inserta una palabra. O(|s|) amortizado
Ejemplo
Trie trie;
trie.insert("casa"); // el trie ahora contiene la palabra "casa"
cout << boolalpha << trie.search("casa"); // imprime true
trie.search(s)Comprueba si existe la palabra completa. O(|s|)
Ejemplo
Trie trie;
trie.insert("casa");
cout << boolalpha << trie.search("casa"); // imprime true
cout << trie.search("cas");               // imprime false