Data Structure Selection Poster

One-page visual decision aid: pick the right data structure in ≤ 30 seconds. Stay in sync with the longer 06-data-structure-selection-guide.md — if a row here disagrees with the guide, trust the guide and update this poster.

---

Decision Tree

What operation do you need?
│
├── Point query only
│   └─-> Array / HashMap                                  O(1)
│
├── Range query, NO updates
│   ├── Idempotent op (min/max/gcd)? -> Sparse Table      O(1) query
│   └── Non-idempotent (sum)?        -> Prefix Sums       O(1) query
│
├── Point update + Range query
│   ├── Invertible operation (sum, xor)?
│   │   └─-> BIT / Fenwick Tree                           O(log n)
│   └── Non-invertible (min/max)?
│       └─-> Segment Tree                                 O(log n)
│
├── Range update + Range query
│   └─-> Segment Tree with Lazy Propagation               O(log n)
│
├── Range update (additive) + Point query
│   └─-> BIT with difference array                        O(log n)
│       (works for additive range updates; not arbitrary
│        range assignments — for those, use lazy seg tree)
│
├── Merge / Split by position or key
│   └─-> Implicit Treap / Splay Tree                      O(log n) amortized
│
├── Dynamic connectivity / Union-Find
│   └─-> DSU (Disjoint Set Union)                         O(α(n)) ~= O(1)
│
├── Ordered set / k-th element / rank
│   ├── Online? -> Policy-based tree (GNU) / Treap        O(log n)
│   └── Offline? -> BIT + coordinate compression          O(log n)
│
├── 2D range queries
│   ├── Static? -> 2D Prefix Sums                         O(1) query
│   └── Dynamic? -> 2D BIT / Merge Sort Tree              O(log² n)
│
└── Persistent (keep old versions)
    └─-> Persistent Segment Tree                          O(log n), O(n log n) space

---

Comparison Table

DS               Build    Pt Upd   Rng Qry  Rng Upd  Space    Notes
───────────────────────────────────────────────────────────────────────
Array            O(n)     O(1)     O(n)     O(n)     O(n)     baseline
Prefix Sums      O(n)     -        O(1)     -        O(n)     static only
Sparse Table     O(n lg)  -        O(1)     -        O(n lg)  idempotent ops
BIT / Fenwick    O(n)     O(lg)    O(lg)    O(lg)*   O(n)     *range via diff
Segment Tree     O(n)     O(lg)    O(lg)    -        O(4n)    non-invertible ok
Lazy Seg Tree    O(n)     O(lg)    O(lg)    O(lg)    O(4n)    range-range
Treap            O(n lg)  O(lg)    O(lg)    O(lg)    O(n)     merge/split
DSU              O(n)     -        -        -        O(n)     union/find
Policy Tree      O(n lg)  O(lg)    O(lg)    -        O(n)     order statistics
Persistent ST    O(n)     O(lg)    O(lg)    -        O(n lg)  versioned

lg = log₂ n. All complexities worst-case unless noted.

---

Quick Pick Rules of Thumb

 ① "Sum/xor on a range, point updates"         -> BIT first.  Simple and fast.
 ② "Min/max on a range, point updates"          -> Segment Tree.
 ③ "Range add + range sum"                      -> Lazy Seg Tree.
 ④ "Static range min/max, tons of queries"      -> Sparse Table for O(1).
 ⑤ "Insert/delete/split at arbitrary position"  -> Implicit Treap.
 ⑥ "Union two sets, check connectivity"         -> DSU.  Nothing else needed.
 ⑦ "k-th smallest in a range"                   -> Persistent Seg Tree / Merge Sort Tree.
 ⑧ "Need old versions after updates"            -> Persistent Seg Tree.
 ⑨  When in doubt: Segment Tree.  It handles almost everything.

---

See also: 06-data-structure-selection-guide.md for detailed discussion.