guest@cp-base:~/home$

Data Structures

(12)

Essential data structures for CP

$ls data-structures/|wc -l12 templates found

template_trie.cpp

Trie

[Data Structures]

Prefix tree for string storage with insert, search, prefix check, and erase in O(|s|).

#trie#prefix-tree#string+1

$ cat trie

template_splay-tree.cpp

Splay Tree

[Data Structures]

Self-adjusting BST with O(log n) amortized operations via splay rotations.

#splay-tree#bst#self-adjusting+1

$ cat splay-tree

template_ordered-set.cpp

Ordered Set

[Data Structures]

Policy-based order-statistics tree — find k-th element and count elements less than x in O(log n).

#ordered-set#pbds#order-statistics+1

$ cat ordered-se..

template_monotonic-stack.cpp

Monotonic Stack

[Data Structures]

Next/previous greater/smaller element queries in O(n) using a monotonic stack.

#monotonic-stack#next-greater#next-smaller+1

$ cat monotonic-..

template_monotonic-queue.cpp

Monotonic Queue

[Data Structures]

Sliding window min/max in O(1) amortized using the two-stack queue pattern.

#monotonic-queue#sliding-window#deque+1

$ cat monotonic-..

template_link-cut-tree.cpp

Link-Cut Tree

[Data Structures]

Dynamic forest structure supporting link, cut, and path queries in O(log n) amortized.

#link-cut-tree#splay#dynamic-tree+1

$ cat link-cut-t..

template_implicit-splay-tree.cpp

Implicit Splay Tree

[Data Structures]

Index-keyed splay tree for sequence operations — insert, erase, range query with lazy propagation.

#splay-tree#implicit#sequence+2

$ cat implicit-s..

template_hld.cpp

Heavy-Light Decomposition

[Data Structures]

Decomposes a tree into chains for O(log^2 n) path queries using a segment tree.

#hld#heavy-light#decomposition+2

$ cat hld

template_heap.cpp

Binary Heap

[Data Structures]

Min/max binary heap with push, pop, and top in O(log n).

#heap#priority-queue#binary-heap

$ cat heap

template_dsu.cpp

DSU

[Data Structures]

Disjoint Set Union with path compression and union by size in near-constant amortized time.

#dsu#union-find#disjoint-set+1

$ cat dsu

template_binary-trie.cpp

Binary Trie

[Data Structures]

Trie on bit representation of integers — supports insert, erase, and XOR maximum query.

#binary-trie#xor#bit+2

$ cat binary-tri..

template_binary-search-tree.cpp

Binary Search Tree

[Data Structures]

Basic BST with insert, delete, search, min/max, and all four traversal orders.

#bst#binary-search-tree#traversal

$ cat binary-sea..