Segment Trees

Basic idea

A balanced binary tree over array intervals: each node stores an aggregate (sum/min/gcd/…) of its range. Supports point/range update and range query in $O(\log n)$, and is far more flexible than a Fenwick tree (any associative op, lazy propagation).

Key formulas

• Build: $O(n)$
• Range query / point update: $O(\log n)$
• Range update with lazy propagation: $O(\log n)$
• Space: $4n$ nodes

Siblings

• Adaptive Radix Tree
• Bloom filter
• Cache Oblivious Algorithms & Datastructures
• Count-min sketch
• CTrie
• Disjoint Set
• Fenwick tree
• Fibonacci heaps
• Finger-Trees
• GeoHash
• Hash Array Mapped Tries
• Hash Tables
• Hilbert-R Tree
• HyperLogLog
• Judy Arrays
• k-d Tree
• Links
• M Tree
• Pairing heaps
• R tree
• RRB-Trees
• Sparse Sets
• Succint Datastructures