data-structures

Data structures

Ordered from silver through advanced.

Coordinate compression [silver]

• CoordinateCompression.h. Sort unique values and map them back to ranks.

Fenwick tree [gold]

• FenwickTree.h. Prefix sums with point updates.

Segment tree [gold]

• SegmentTree.h. Recursive segment tree.
• IterativeSegmentTree.h. Iterative segment tree.

Lazy segment tree [platinum]

• LazySegmentTree.h. Segment tree with lazy range updates.

Mo's algorithm [platinum]

• Mo.h. Offline range queries in blocks.
• mo_algorithm/. A solved Mo problem.

Sparse segment tree [platinum]

• SparseSegmentTree.h. A segment tree that allocates only visited nodes.

Square root decomposition [platinum]

• SRD.h. Blocks over a one-dimensional array.

Persistent segment tree [advanced]

• PersistentSegmentTree.h. Persistent sparse segment tree.