Data Structures

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

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

Static range query structure — O(1) for idempotent operations (min/max/gcd), O(log n) for non-idempotent.

Nested segment tree for 2D point update and rectangle queries in O(log n * log m).

Classic segment tree with point update and range query for any associative operation.

Segment tree preserving all versions via path copying — O(log n) per update, O(n + q log n) total memory.

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

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

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

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

Segment tree with lazy propagation — supports range updates and range queries in O(log n).

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

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

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

Fenwick tree supporting both range add and range sum queries using two BITs.

2D Binary Indexed Tree for point updates and rectangle sum queries in O(log n * log m).

Binary Indexed Tree for prefix sum queries and point updates in O(log n).

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

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

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