Data Structures & Algorithms

Data Structures

This branch focuses on structures that trade memory, invariants, or amortization for faster updates and queries.

16 published notes

3 planned topics

8 advanced or expert notes

basic starting level

Back to DSA Competitive Programming

Category Overview

Data Structures

Range-query workhorses, balanced trees, and dynamic forest tools.

Raw TeX

Overview

This branch collects the data structures I expect to reach for repeatedly in contest code: small range-query tools, balanced trees, and dynamic structures that let an update stay local while the answer remains global.

How I Organize the Notes

I try to separate the notes by the kind of invariant they maintain:

prefix-based structures such as Fenwick trees,
interval-based structures such as segment trees,
set / sequence BSTs such as treaps and splay trees,
dynamic-forest structures such as link-cut trees.
That makes it easier to see which tool to try when the problem statement changes one assumption.

Difficulty Bands

How this branch is distributed

The labels are not cosmetic. They are there to signal the amount of prerequisite structure and implementation fragility you should expect before opening the note.

basic: 5 intermediate: 3 advanced: 6 expert: 2

5 basic

basic

These are the shortest on-ramp notes in this category and the ones most likely to be usable immediately in contest practice.

Fenwick Tree, Monotonic Stack and Queue, Segment Tree, Sparse Table, Disjoint Set Union

3 intermediate

intermediate

These notes assume the base routine is already familiar and focus on the first real structural upgrades.

Two-Dimensional Fenwick Tree, Lazy Segment Tree, Ordered Set (Policy-Based Data Structures)

6 advanced

advanced

These are the notes where proofs, reductions, or implementation details become the main bottleneck.

Treap, Li Chao Tree, Persistent Segment Tree, DSU Rollback, Cartesian Tree, Wavelet Tree

2 expert

expert

These are the pointer-heavy or amortized tools that are usually worth revisiting only after the rest of the branch is comfortable.

Splay Tree, Link-Cut Tree

Published notes

What is already written

These are the finished note pages in this category, each with rendered TeX, C++ code, references, and practice suggestions.

basic

Fenwick Tree

A compact range-query structure for point updates, prefix sums, and frequency-based order statistics.

range queries prefix sums / binary lifting

basic

Monotonic Stack and Queue

Maintain candidates in sorted order of value so next-greater and sliding-window extrema can be updated in linear time.

stack deque / linear time

intermediate

Two-Dimensional Fenwick Tree

Extend the Fenwick tree idea to point updates and rectangle sums on a grid.

fenwick tree 2d / grid queries

basic

Segment Tree

The general-purpose interval tree for logarithmic range queries and updates when Fenwick is too small.

range queries interval decomposition / iterative tree

intermediate

Lazy Segment Tree

The standard extension of a segment tree when range updates must stay logarithmic too.

range updates lazy propagation / interval tree

basic

Sparse Table

A static range-query structure that turns immutable RMQ-style queries into O(1) lookups.

static queries rmq / power-of-two decomposition

basic

Disjoint Set Union

Union-find for dynamic connectivity and component bookkeeping when edges only merge components.

connectivity union find / amortized

advanced

Treap

A randomized BST built from split and merge, with order statistics and clean structural recursion.

balanced bst split merge / order statistics

expert

Splay Tree

A self-adjusting BST that pays for flexibility with amortized analysis instead of explicit balance invariants.

self-adjusting bst amortized analysis / split merge

010

expert

Link-Cut Tree

A dynamic-forest structure built on splay trees for link, cut, reroot, and path-query operations.

dynamic forest splay tree / path queries

011

intermediate

Ordered Set (Policy-Based Data Structures)

An indexed balanced tree for order statistics when std::set is not enough and a full custom BST is overkill.

order statistics GNU PBDS / balanced tree

012

advanced

Li Chao Tree

A segment-tree-style structure for maintaining a dynamic lower envelope of lines under point queries.

lines DP optimization / dynamic hull

013

advanced

Persistent Segment Tree

Path-copy only the changed nodes so every update creates a new version without destroying the old one.

persistence range queries / versioned structure

014

advanced

DSU Rollback

A union-find variant that can undo merges, which is the missing piece behind offline dynamic connectivity.

union find rollback / offline

015

advanced

Cartesian Tree

Build a tree whose inorder traversal is the array order and whose heap property exposes range minima or maxima.

tree construction rmq / monotonic stack

016

advanced

Wavelet Tree

Recursively partition values so k-th order statistics and frequency queries on subarrays can be answered quickly.

order statistics range queries / value partition

Study Order

Next topics in this branch

These are still intentionally shown as planned or outline topics rather than shallow filler. The branch should feel incomplete in honest places instead of fake-complete everywhere.

Priority queue planned Persistent DSU outline Segment tree beats outline

Show raw files

Category TeX sourcecompetitive_programming/dsa/data-structures/index.tex

Data Structures

Data Structures

Overview

How I Organize the Notes

How this branch is distributed

What is already written

Fenwick Tree

Monotonic Stack and Queue

Two-Dimensional Fenwick Tree

Segment Tree

Lazy Segment Tree

Sparse Table

Disjoint Set Union

Treap

Splay Tree

Link-Cut Tree

Ordered Set (Policy-Based Data Structures)

Li Chao Tree

Persistent Segment Tree

DSU Rollback

Cartesian Tree

Wavelet Tree

Recommended order to read this branch

Fenwick Tree

Monotonic Stack and Queue

Two-Dimensional Fenwick Tree

Segment Tree

Lazy Segment Tree

Sparse Table

Disjoint Set Union

Treap

Splay Tree

Link-Cut Tree

Ordered Set (Policy-Based Data Structures)

Li Chao Tree

Persistent Segment Tree

DSU Rollback

Cartesian Tree

Wavelet Tree

Next topics in this branch

Source Files and Assets