Search tools and guides ⌘K
II · Trees, with shape

Segment tree

Range queries in logarithmic time.

1977 · Jon Bentley
The story

Bentley introduced segment trees in his thesis on computational geometry. Pre-aggregate the array at every power-of-two granularity; answer any range query as the union of O(log n) covering nodes. Generalises to any associative aggregate: sum, min, max, GCD, matrix multiplication.

How it works

A balanced binary tree where each leaf is one array element and each internal node holds the aggregate of its leaves' range. Range query walks two pointers up the tree picking off the largest fully-contained nodes. Lazy propagation extends it to range updates in O(log n) amortised.

Where it lives

Editor minimum-indentation queries. Database query-optimiser cost arithmetic. Time-series percentile rollups. Every "competitive programming" interview round above easy.

The key insight

A segment tree handles any associative aggregate; a Fenwick tree (BIT) is faster but only handles invertible ones (sum, XOR). Pick segment for min/max/GCD; pick Fenwick for sum.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree. Splay tree No metadata — and surprising amortised guarantees.
Across the cabinet
IV Count-Min sketch Approximate frequencies, in tiny memory. IV MinHash Set similarity, in a few hashes. IV t-digest Quantiles, fairly accurate, fully streaming. V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it. V Gap buffer A buffer with a hole at the cursor.
← All data structures