ICPC

Estructuras de Datos
Interfaces de la librería estándar · Python & C++

Array · Stack · Queue · Deque · Heap · Set · Map · Segment Tree · Trie

Referencia rápida para la ICPC ■

ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

Contenido
■■ 1. Array / List — list, vector
■■ 2. Stack — list/deque, stack
■■ 3. Queue — deque/queue, queue
■■ 4. Deque (doble extremo) — deque, deque
■■ 5. Heap / Priority Queue — heapq, priority_queue
■■ 6. Set & Multiset — set/SortedList, set/multiset
■■ 7. Map (Diccionario) — dict/Counter, map/unordered_map
■■ 8. Linked List — [Link], list
■■ 9. Segment Tree — implementación manual
■■ 10. Trie — implementación manual
■■ 11. Tabla de complejidades globales

Página 2
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

1. Array / List — list · vector

ICPC USE Secuencias indexadas. Base de casi todo. Acceso O(1). Append amortizado O(1).

Operación Python C++ Complejidad

Acceso por índice a[i] a[i] O(1)

Append al final [Link](x) a.push_back(x) O(1) amort.

Insertar en medio [Link](i,x) [Link](it,x) O(n)

Eliminar al final [Link]() a.pop_back() O(1)

Eliminar por índice [Link](i) [Link]([Link]()+i) O(n)

Tamaño len(a) [Link]() O(1)

Ordenar [Link]() sort([Link](),[Link]()) O(n log n)

Búsqueda lineal x in a find(begin,end,x) O(n)

Slice/subarray a[l:r] vector([Link]()+l,[Link]()+r) O(k)

Rellenar [0]*n vector<int>(n,0) O(n)

Python – list

■ Python

a = [] # lista vacía
a = [0] * 10 # 10 ceros
a = list(range(n)) # [0,1,...,n-1]
[Link](x) # agregar al final
[Link]() # eliminar y retornar último
[Link](i) # eliminar índice i
[Link](i, x) # insertar en posición i
[Link](x) # eliminar primera ocurrencia de x
[Link]() # in-place
[Link](key=lambda x: -x) # descendente
b = sorted(a) # nueva lista ordenada
[Link]() # in-place
b = a[::-1] # nueva lista invertida
[Link](x) # primer índice de x (ValueError si no existe)
[Link](x) # cuántas veces aparece x
x in a # True/False (O(n))
a[l:r] # slice [l, r)
a[l:r:step] # con paso
a + b # concatenar (nueva lista)
[Link](b) # agregar todos los de b a a
# Comprensiones
cuadrados = [x*x for x in range(10)]
pares = [x for x in a if x % 2 == 0]
matriz = [[0]*cols for _ in range(rows)] # CORRECTO para 2D
# min / max / sum
print(min(a), max(a), sum(a))

■■ C++

Página 3
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

#include <bits/stdc++.h>
using namespace std;
vector<int> a; // vacío
vector<int> a(10, 0); // 10 ceros
vector<int> a = {1, 2, 3};
a.push_back(x); // agregar al final O(1) amort.
a.pop_back(); // eliminar último O(1)
[Link]([Link]() + i, x); // insertar en i O(n)
[Link]([Link]() + i); // eliminar índice i O(n)
sort([Link](), [Link]()); // ascendente
sort([Link](), [Link](), greater<int>()); // descendente
reverse([Link](), [Link]());
// Búsqueda binaria (requiere ordenado)
auto it = lower_bound([Link](), [Link](), x);
auto it = upper_bound([Link](), [Link](), x);
bool found = binary_search([Link](), [Link](), x);
*min_element([Link](), [Link]());
*max_element([Link](), [Link]());
accumulate([Link](), [Link](), 0LL); // suma (0LL para long long)
// 2D vector
vector<vector<int>> mat(rows, vector<int>(cols, 0));

■ En Python, nunca hagas [[0]*cols]*rows para matrices 2D: todas las filas apuntan al mismo objeto. Usa siempre list comprehension.

Página 4
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

2. Stack (Pila) — list · stack<>

ICPC USE LIFO. Paréntesis balanceados, historial, DFS iterativo, expresiones, monotonic stack.

Operación Python C++ Complejidad

Push (insertar) [Link](x) [Link](x) O(1)

Pop (sacar) [Link]() [Link]() O(1)

Peek (cima) a[-1] [Link]() O(1)

¿Vacío? not a [Link]() O(1)

Tamaño len(a) [Link]() O(1)

Python – usar list como stack

■ Python

stack = []
[Link](x) # push
[Link]() # pop → retorna y elimina el tope
stack[-1] # peek → solo ver el tope (no eliminar)
not stack # True si vacío
len(stack) # tamaño
# Ejemplo: paréntesis balanceados
def is_balanced(s):
stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for c in s:
if c in '([{':
[Link](c)
elif c in ')]}':
if not stack or stack[-1] != pairs[c]:
return False
[Link]()
return not stack
# Monotonic stack – siguiente mayor elemento
def next_greater(arr):
n = len(arr)
result = [-1] * n
stack = [] # guarda índices
for i in range(n):
while stack and arr[stack[-1]] < arr[i]:
result[[Link]()] = arr[i]
[Link](i)
return result

■■ C++

Página 5
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

#include <stack>
stack<int> s;
[Link](x); // insertar
[Link](); // eliminar tope (no retorna)
[Link](); // ver tope
[Link](); // bool
[Link](); // tamaño
// Monotonic stack en C++
vector<int> next_greater(vector<int>& a){
int n = [Link]();
vector<int> res(n, -1);
stack<int> st;
for(int i=0;i<n;i++){
while(![Link]() && a[[Link]()]<a[i]){
res[[Link]()]=a[i]; [Link]();
}
[Link](i);
}
return res;
}

■ En Python no existe una clase Stack en stdlib. Usa list: append = push, pop() = pop. Es O(1) en ambos extremos del final.

Página 6
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

3. Queue (Cola) — deque · queue<>

ICPC USE FIFO. BFS, simulaciones por turnos, procesamiento en orden de llegada.

Operación Python C++ Complejidad

Enqueue (insertar) [Link](x) [Link](x) O(1)

Dequeue (sacar) [Link]() [Link]() O(1)

Frente q[0] [Link]() O(1)

Atrás q[-1] [Link]() O(1)

¿Vacío? not q [Link]() O(1)

Python – [Link] como Queue

■ Python

from collections import deque

q = deque()
[Link](x) # enqueue (insertar al final)
[Link]() # dequeue (sacar del frente) → O(1) !!!
q[0] # ver el frente
q[-1] # ver el final
not q # True si vacía
# NO uses [Link](0) → es O(n)
# USA [Link]() → O(1)
# BFS con deque
from collections import deque
def bfs(graph, start):
visited = {start}
q = deque([start])
while q:
node = [Link]()
for nei in graph[node]:
if nei not in visited:
[Link](nei)
[Link](nei)

■■ C++

#include <queue>
queue<int> q;
[Link](x); // enqueue
[Link](); // dequeue (no retorna)
[Link](); // ver frente
[Link](); // ver atrás
[Link](); // bool
[Link](); // tamaño
// BFS en C++
queue<int> bfs_q;
bfs_q.push(src);
vector<bool> vis(n+1, false);
vis[src] = true;
while(!bfs_q.empty()){
int u = bfs_q.front(); bfs_q.pop();
for(int v : adj[u])
if(!vis[v]){ vis[v]=true; bfs_q.push(v); }
}

Página 7
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

■ NUNCA uses [Link](0) en Python: es O(n) porque desplaza todos los elementos. [Link]() es O(1).

Página 8
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

4. Deque (Cola Doble) — deque · deque<>

ICPC USE Insertar/eliminar en ambos extremos. Sliding window máximo/mínimo. BFS/DFS combinado.

Operación Python C++ Complejidad

Push frente [Link](x) d.push_front(x) O(1)

Push atrás [Link](x) d.push_back(x) O(1)

Pop frente [Link]() d.pop_front() O(1)

Pop atrás [Link]() d.pop_back() O(1)

Acceso índice d[i] d[i] O(1)

Rotar [Link](k) — O(k)

Python – [Link]

■ Python

from collections import deque

d = deque()
d = deque([1,2,3])
d = deque(maxlen=k) # tamaño fijo, auto-descarta el lado opuesto
[Link](x) # insertar al final
[Link](x) # insertar al frente
[Link]() # eliminar del final
[Link]() # eliminar del frente
d[0] # ver frente
d[-1] # ver final
d[i] # acceso por índice (más lento que list)
[Link](k) # rotar k posiciones a la derecha (k<0 → izquierda)
[Link](iterable) # agregar al final
[Link](iterable) # agregar al frente (invierte el iterable)
# Sliding window máximo – O(n)
def sliding_max(arr, k):
d = deque() # guarda ÍNDICES, valor decreciente
result = []
for i, x in enumerate(arr):
while d and arr[d[-1]] <= x:
[Link]()
[Link](i)
if d[0] <= i - k: # fuera de la ventana
[Link]()
if i >= k - 1:
[Link](arr[d[0]])
return result

■■ C++

Página 9
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

#include <deque>
deque<int> d;
d.push_back(x); d.push_front(x);
d.pop_back(); d.pop_front();
[Link](); [Link]();
d[i]; // acceso aleatorio O(1)
[Link](); [Link]();
// Sliding window max en C++
vector<int> sliding_max(vector<int>& a, int k){
deque<int> dq;
vector<int> res;
for(int i=0;i<(int)[Link]();i++){
while(![Link]() && a[[Link]()]<=a[i]) dq.pop_back();
dq.push_back(i);
if([Link]()<=i-k) dq.pop_front();
if(i>=k-1) res.push_back(a[[Link]()]);
}
return res;
}

■ La deque con maxlen en Python es perfecta para ventanas fijas: al hacer append cuando está llena, automáticamente descarta del
lado contrario.

Página 10
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

5. Heap / Priority Queue — heapq · priority_queue<>

ICPC USE K-ésimo mayor/menor, Dijkstra, Prim, merge de listas ordenadas, scheduling.

Operación Python C++ Complejidad

Insertar [Link](h,x) [Link](x) O(log n)

Extraer mínimo [Link](h) [Link]()+pop() O(log n)

Ver mínimo h[0] [Link]() O(1)

Heapify lista [Link](a) make_heap() O(n)

n-ésimo menor [Link](k,a) — O(n log k)

¿Vacío? not h [Link]() O(1)

Python – heapq (siempre min-heap)

■ Python

import heapq
h = []
[Link](h, x) # insertar O(log n)
[Link](h) # extraer mínimo O(log n)
h[0] # ver mínimo sin extraer O(1)
[Link](a) # convertir lista en heap in-place O(n)
[Link](k, a) # k menores (no destruye la lista)
[Link](k, a) # k mayores
# MAX-HEAP → negar los valores
[Link](h, -x)
max_val = -[Link](h)
# Heap de tuplas → ordena por primer elemento
[Link](h, (prioridad, dato))
prio, dato = [Link](h)
# Dijkstra pattern
dist = [float('inf')] * (n+1)
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = [Link](heap)
if d > dist[u]: continue
for w, v in graph[u]:
if dist[u]+w < dist[v]:
dist[v] = dist[u]+w
[Link](heap, (dist[v], v))
# K-ésimo mayor elemento
import heapq
def kth_largest(arr, k):
h = arr[:k]
[Link](h) # min-heap de tamaño k
for x in arr[k:]:
if x > h[0]:
[Link](h, x)
return h[0]

■■ C++

Página 11
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

#include <queue>
// MAX-HEAP (por defecto)
priority_queue<int> pq;
// MIN-HEAP
priority_queue<int, vector<int>, greater<int>> pq;
// Con pares (min por distancia)
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
[Link](x); // insertar O(log n)
[Link](); // eliminar tope O(log n) — no retorna valor
[Link](); // ver tope O(1)
[Link](); [Link]();

■ [Link](h, x) es más eficiente que heappop+heappush cuando el nuevo elemento podría ser mayor que el mínimo actual.

Página 12
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

6. Set & Multiset — set/frozenset · set<>/multiset<>

ICPC USE Pertenencia O(1) (hash set). Conjunto ordenado con sucesor/predecesor (tree set). Eliminar duplicados.

Operación Python C++ Complejidad

Insertar [Link](x) [Link](x) O(1)* / O(log n)

Eliminar [Link](x) [Link](x) O(1)* / O(log n)

Pertenencia x in s [Link](x) O(1)* / O(log n)

Mínimo/Máximo min(s) / max(s) *[Link]() / *[Link]() O(n) / O(1)

Sucesor — s.upper_bound(x) O(log n)

Unión a | b merge / set_union O(n log n)

Intersección a & b set_intersection O(n log n)

* Python set = hash set. C++ set<> = árbol rojo-negro (ordenado).

Python – set (hash set) y operaciones

■ Python

# SET – hash set, sin orden garantizado

s = set()
s = {1, 2, 3}
s = set(lista) # elimina duplicados
[Link](x) # O(1) promedio
[Link](x) # O(1) – no lanza error si no existe
[Link](x) # O(1) – lanza KeyError si no existe
x in s # O(1)
len(s)
# Operaciones de conjuntos
a | b # unión
a & b # intersección
a - b # diferencia (en a pero no en b)
a ^ b # diferencia simétrica
a <= b # a es subconjunto de b
[Link](b) # sin elementos en común
# Eliminar duplicados conservando orden (Python 3.7+)
unique = list([Link](lista))
# Iterar en orden → convertir a sorted
for x in sorted(s):
print(x)
# frozenset → hashable (sirve como clave de dict o elemento de set)
fs = frozenset([1, 2, 3])

■■ C++

Página 13
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

#include <set>
#include <unordered_set>
// SET ORDENADO – árbol rojo-negro O(log n)
set<int> s;
[Link](x);
[Link](x); // por valor
[Link]([Link](x)); // por iterador
[Link](x); // 0 o 1
[Link](x) != [Link](); // contiene x
*[Link](); // mínimo
*[Link](); // máximo
auto it = s.lower_bound(x); // primer elemento >= x
auto it = s.upper_bound(x); // primer elemento > x
// MULTISET – permite duplicados
multiset<int> ms;
[Link](x);
[Link]([Link](x)); // elimina UNA ocurrencia
[Link](x); // cuántas veces aparece
// HASH SET – O(1) promedio, sin orden
unordered_set<int> hs;
[Link](x); [Link](x); [Link](x);

■ Cuando necesitas sucesor/predecesor en Python, usa SortedList de sortedcontainers (si está disponible en el juez). En C++, set<> lo
da gratis con lower_bound.

Página 14
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

7. Map (Diccionario) — dict/Counter · map<>/unordered_map<>

ICPC USE Frecuencias, memoización, índices inversos, grafos con pesos, cualquier clave→valor.

Operación Python C++ Complejidad

Insertar/actualizar d[k] = v m[k] = v O(1)* / O(log n)

Acceso d[k] m[k] o [Link](k) O(1)* / O(log n)

Borrar del d[k] [Link](k) O(1)* / O(log n)

¿Contiene? k in d [Link](k) O(1)* / O(log n)

Valor default [Link](k, 0) [Link](k)?m[k]:0 O(1)*

Iteración [Link]() for(auto& [k,v]:m) O(n)

Ordenado por clave sorted([Link]()) map<K,V> O(n log n)

Python – dict y Counter

■ Python

Página 15
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

# DICT – hash map O(1) promedio

d = {}
d = {'a': 1, 'b': 2}
d = dict(zip(claves, valores))
d[k] = v # insertar / actualizar
d[k] # acceso (KeyError si no existe)
[Link](k, default) # acceso seguro con default
del d[k] # borrar
k in d # pertenencia O(1)
[Link](k, None) # borrar y retornar (None si no existe)
# Iterar
for k in d: # claves
for v in [Link](): # valores
for k, v in [Link](): # pares
# defaultdict – valor por defecto automático
from collections import defaultdict
freq = defaultdict(int) # default 0
graph = defaultdict(list) # default []
freq[x] += 1 # no lanza KeyError
# Counter – frecuencias
from collections import Counter
freq = Counter(lista) # {elem: count, ...}
freq = Counter(string)
freq.most_common(k) # top k más frecuentes
freq[x] # 0 si no existe (no KeyError)
[Link](otra_lista) # agregar más conteos
total = sum([Link]())
# Memoización con dict
memo = {}
def fib(n):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
# O usa functools.lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n<=1 else fib(n-1)+fib(n-2)

■■ C++

Página 16
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

#include <map>
#include <unordered_map>
// MAP ORDENADO por clave – O(log n)
map<string, int> m;
m["key"] = val; // insertar / actualizar
m["key"]; // acceso (crea si no existe!)
[Link]("key"); // acceso seguro (lanza si no existe)
[Link]("key"); // 0 o 1
[Link]("key");
for(auto& [k, v] : m) // iterar (C++17)
cout << k << " " << v << "
";
m.lower_bound(k); // iterador al primer >= k
// UNORDERED_MAP – hash O(1) promedio
unordered_map<int,int> um;
um[k] = v;
[Link](k);
[Link](k) != [Link]();
// Frecuencias
unordered_map<int,int> freq;
for(int x : arr) freq[x]++;

■ defaultdict(int) es tu mejor amigo para contar frecuencias. lru_cache convierte cualquier función recursiva en DP memoizado sin
código extra.

Página 17
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

8. Linked List — deque · list<>

ICPC USE Inserciones/eliminaciones O(1) en posición conocida. En ICPC rara vez se usa directamente; deque cubre casi todos los casos.

Operación Python C++ Complejidad

Insertar al frente [Link](x) l.push_front(x) O(1)

Insertar al final [Link](x) l.push_back(x) O(1)

Borrar al frente [Link]() l.pop_front() O(1)

Borrar por valor [Link](x) [Link](x) O(n)

Acceso por índice d[i] O(n) — O(n)

Insertar en medio — [Link](it, x) O(1)

Python – simular con deque o lista de nodos

■ Python

from collections import deque

# deque cubre el 99% de los casos de linked list en ICPC
d = deque()
[Link](x) # O(1) al frente
[Link](x) # O(1) al final
[Link]() # O(1) sacar del frente
[Link]() # O(1) sacar del final
[Link](x) # O(n) – primer x encontrado
# Implementación manual (si el problema lo exige)
class Node:
def __init__(self, val):
[Link] = val
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def prepend(self, val):
node = Node(val)
[Link] = [Link]
[Link] = node
def to_list(self):
result, cur = [], [Link]
while cur:
[Link]([Link])
cur = [Link]
return result
# Invertir linked list (patrón ICPC)
def reverse(head):
prev, cur = None, head
while cur:
nxt = [Link]
[Link] = prev
prev = cur
cur = nxt
return prev

■■ C++

Página 18
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

#include <list>
list<int> l;
l.push_front(x); l.push_back(x);
l.pop_front(); l.pop_back();
[Link](); [Link]();
[Link](it, x); // insertar antes del iterador O(1)
[Link](it); // O(1) con iterador
[Link](x); // O(n) borra todas las ocurrencias
[Link](); [Link]();
[Link](); [Link]();
// Iterar
for(int x : l) cout << x << " ";

■ En ICPC casi nunca necesitas implementar una linked list desde cero. Si el problema requiere insert/delete rápido con orden,
considera usar un ordered set o un BIT en vez.

Página 19
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

9. Segment Tree — implementación manual

ICPC USE Consultas de rango (suma, mínimo, máximo) Y actualizaciones puntuales en O(log n). Si solo consultas: usa prefix sum.

Operación Python C++ Complejidad

Build O(n) O(n) O(n)

Update puntual O(log n) O(log n) O(log n)

Query de rango O(log n) O(log n) O(log n)

Update de rango O(log n)* O(log n)* O(log n) con lazy

Python – Segment Tree suma

■ Python

class SegTree:
def __init__(self, data):
self.n = len(data)
[Link] = [0] * (4 * self.n)
self._build(data, 1, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
[Link][node] = data[start]
else:
mid = (start + end) // 2
self._build(data, 2*node, start, mid)
self._build(data, 2*node+1, mid+1, end)
[Link][node] = [Link][2*node] + [Link][2*node+1]
def update(self, idx, val, node=1, start=0, end=None):
if end is None: end = self.n - 1
if start == end:
[Link][node] = val
else:
mid = (start + end) // 2
if idx <= mid:
[Link](idx, val, 2*node, start, mid)
else:
[Link](idx, val, 2*node+1, mid+1, end)
[Link][node] = [Link][2*node] + [Link][2*node+1]
def query(self, l, r, node=1, start=0, end=None):
if end is None: end = self.n - 1
if r < start or end < l: return 0 # fuera del rango
if l <= start and end <= r: return [Link][node] # dentro
mid = (start + end) // 2
return ([Link](l, r, 2*node, start, mid) +
[Link](l, r, 2*node+1, mid+1, end))
# Uso
st = SegTree([1, 3, 5, 7, 9])
print([Link](1, 3)) # suma arr[1..3] = 15
[Link](2, 10) # arr[2] = 10
print([Link](0, 4)) # nueva suma total

■■ C++

Página 20
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

// C++ Segment Tree iterativo (más rápido)

const int MAXN = 1e5+5;
int tree[4*MAXN];
void build(int* a, int node, int s, int e){
if(s==e){ tree[node]=a[s]; return; }
int m=(s+e)/2;
build(a,2*node,s,m); build(a,2*node+1,m+1,e);
tree[node]=tree[2*node]+tree[2*node+1];
}
void update(int node,int s,int e,int i,int v){
if(s==e){ tree[node]=v; return; }
int m=(s+e)/2;
if(i<=m) update(2*node,s,m,i,v);
else update(2*node+1,m+1,e,i,v);
tree[node]=tree[2*node]+tree[2*node+1];
}
int query(int node,int s,int e,int l,int r){
if(r<s||e<l) return 0;
if(l<=s&&e<=r) return tree[node];
int m=(s+e)/2;
return query(2*node,s,m,l,r)+query(2*node+1,m+1,e,l,r);
}

■ Cambia la operación de combinación (suma por min/max/gcd) para adaptar a otros tipos de query. Para updates de rango añade
'lazy propagation'.

Página 21
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

10. Trie (Árbol de Prefijos) — implementación manual

ICPC USE Búsqueda de prefijos, autocompletado, contar strings con prefijo común, XOR máximo con trie binario.

Operación Python C++ Complejidad

Insertar palabra O(L) O(L) L = longitud

Buscar palabra O(L) O(L)

Buscar prefijo O(L) O(L)

Espacio O(N·L) O(N·L) N = num palabras

Python – Trie con dict

■ Python

class Trie:
def __init__(self):
[Link] = {}
def insert(self, word):
node = [Link]
for c in word:
node = [Link](c, {})
node['#'] = True # marca fin de palabra
def search(self, word):
node = [Link]
for c in word:
if c not in node: return False
node = node[c]
return '#' in node # ¿palabra completa?
def starts_with(self, prefix):
node = [Link]
for c in prefix:
if c not in node: return False
node = node[c]
return True
def count_prefix(self, prefix):
# Contar palabras con este prefijo (necesita contador)
node = [Link]
for c in prefix:
if c not in node: return 0
node = node[c]
# DFS para contar '#'
def dfs(n):
cnt = 1 if '#' in n else 0
for k,v in [Link]():
if k != '#': cnt += dfs(v)
return cnt
return dfs(node)
# Uso
trie = Trie()
for word in ["apple","app","apply","banana"]:
[Link](word)
print([Link]("app")) # True
print(trie.starts_with("app")) # True
print(trie.starts_with("ban")) # True
print([Link]("ap")) # False

Página 22
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

■■ C++

// C++ Trie con array (más rápido)

const int ALPHA = 26;
struct Trie {
int ch[26];
bool end;
Trie(){ fill(ch,ch+26,-1); end=false; }
};
vector<Trie> trie(1);
void insert(const string& s){
int cur=0;
for(char c:s){
int x=c-'a';
if(trie[cur].ch[x]==-1){
trie[cur].ch[x]=[Link]();
trie.push_back(Trie());
}
cur=trie[cur].ch[x];
}
trie[cur].end=true;
}
bool search(const string& s){
int cur=0;
for(char c:s){
int x=c-'a';
if(trie[cur].ch[x]==-1) return false;
cur=trie[cur].ch[x];
}
return trie[cur].end;
}

■ Para XOR máximo en arreglos de enteros, usa un Trie binario de 30 bits. Inserta cada número bit a bit (del más significativo al
menos) y busca el complemento.

Página 23
ICPC — ESTRUCTURAS DE DATOS Python · C++ stdlib

11. Tabla de Complejidades Globales

Resumen de todas las estructuras para comparación rápida.

Estructura Acceso Búsqueda Inserción Borrado Espacio Python C++

Array/List O(1) O(n) O(1)* O(n) O(n) list vector

Stack O(n) O(n) O(1) O(1) O(n) list stack

Queue O(n) O(n) O(1) O(1) O(n) deque queue

Deque O(1) O(n) O(1) O(1) O(n) deque deque

Heap (min) O(1) min O(n) O(log n) O(log n) O(n) heapq priority_queue

Hash Set — O(1)* O(1)* O(1)* O(n) set unordered_set

Tree Set — O(log n) O(log n) O(log n) O(n) SortedList** set

Hash Map — O(1)* O(1)* O(1)* O(n) dict unordered_map

Tree Map — O(log n) O(log n) O(log n) O(n) — map

Segment Tree O(log n) O(log n) O(log n) O(log n) O(n) manual manual

Trie O(L) O(L) O(L) O(L) O(NL) manual manual

* Promedio con hash. ** sortedcontainers (puede no estar en el juez).

L = longitud del string/clave. N = número de elementos. * en acceso = amortizado.

¿Cuál estructura usar? – Guía rápida

¿Necesitas acceso por índice? list / vector

¿Solo insertar/sacar por un extremo? Stack (list)

¿Insertar por atrás, sacar por delante? Queue (deque)

¿Insertar/sacar por ambos extremos? Deque

¿Siempre quieres el mínimo/máximo? Heap (heapq / priority_queue)

¿Pertenencia rápida, sin orden? Hash Set (set / unordered_set)

¿Pertenencia + orden + sucesor? Tree Set (set<> en C++)

¿Clave → valor, sin orden? Hash Map (dict / unordered_map)

¿Clave → valor, ordenado? Tree Map (map<> en C++)

¿Queries de rango + updates? Segment Tree

¿Prefijos de strings? Trie

¿Frecuencias de elementos? Counter / unordered_map

Domina Python primero. C++ es solo traducción. ¡Mucho éxito en la ICPC! ■

Página 24