Segment Tree

Segment tree is a hierarchical, balanced binary tree data structure within computation and algorithms that partitions a discrete coordinate domain [0, n − 1] (or a set of geometric intervals) into a recursive hierarchy of canonical sub-intervals, enabling both associative range queries and point or range updates in worst-case O(log n) time after O(n) linear-time construction. In computational geometry, the continuous-interval segment tree was introduced by Jon Louis Bentley in 1977 to store horizontal and vertical line segments and report all segments stabbed by a query point x in O(log n + k) time. In algorithm engineering, the array-based range-query segment tree evaluates any associative monoid aggregation (Sum, Minimum, Maximum, GCD, XOR, or matrix product) over any contiguous subarray A[L..R].

Whereas a Fenwick tree (binary indexed tree) occupies n words of memory and specializes in invertible prefix-cumulative operations such as range sums, a segment tree uses 2n to 4n words of storage but generalizes to non-invertible semigroups (such as Dynamic Range Minimum Queries, where a minimum cannot be recovered by subtracting a prefix from a longer prefix) and supports O(log n) bulk range updates via lazy propagation, as well as O(log n)-space persistent historical snapshots within computational complexity theory.

Recursive Binary Subdivision and the 2 log_2 n Canonical Cover Theorem

Let A[0..n − 1] be an array of n elements over a monoid (M, ⊕, e). A segment tree T over [0, n − 1] is a binary tree in which every node u represents a sub-interval [l_u, r_u] and stores *val*[u] = A[l_u] ⊕ ... ⊕ A[r_u]. Each leaf (l_u = r_u = i) stores A[i], while each internal node (l_u < r_u) splits at midpoint m = ⌊(l_u + r_u)/2⌋ into [l_u, m] and [m + 1, r_u], computing *val*[u] = *val*[left(u)] ⊕ *val*[right(u)] in O(1) time. The tree has 2n − 1 nodes and height ⌈log₂ n⌉, occupying at most 4n words in a 1-indexed heap layout or 2n words in an iterative bottom-up layout.

Proof That Any Query Range [L, R] Decomposes into At Most 2⌈log_2 n⌉ Nodes

To evaluate Query(1, 0, n − 1, L, R) = ⨁_i=L..R A[i], each visited node u falls into one of three cases: (1) Disjoint (r_u < L or l_u > R), returning e; (2) Contained (L ≤ l_u and r_u ≤ R), returning *val*[u] as a canonical node without recursing; or (3) Partial Overlap, recursing on both children. Because at most 2 nodes per tree level can straddle the boundaries L and R (Case 3), at most 2 canonical nodes are selected per level, partitioning [L, R] into at most 2⌈log₂ n⌉ disjoint canonical sub-intervals in O(log n) time.

Lazy Propagation for O(log n) Bulk Range Updates

A point update A[i] ← v updates the single root-to-leaf path in O(log n) time. For bulk range updates on [L, R], lazy propagation stores a deferred operator tag *lazy*[u] at each internal node u. When a range update covers a canonical node u (Case 2), it updates *val*[u] in O(1) time, composes the update into *lazy*[u], and halts without visiting descendants; whenever a later query or update descends through u (Case 3), Push-Down(u) transfers *lazy*[u] to u's children in O(1) time. Segment Tree Beats (Ji, 2016) extends lazy propagation to range clamping (A[i] ← min(A[i], x)) in O(log n) amortized time by tracking the first and second maxima (max₁, cnt, max₂) per node.

Persistent Segment Trees and Bentley's Geometric Stabbing Tree

Replacing array indexing with left/right pointers enables path-copying persistence: because a point update modifies only the ⌈log₂ n⌉ + 1 nodes along a single root-to-leaf path, allocating O(log n) new nodes along that path while sharing unmodified sibling subtrees with the prior version creates an immutable historical snapshot per update, answering 2D orthogonal range counting and subarray k-th order statistic queries in O(log n) time. In Bentley's 1977 geometric formulation, storing N intervals [a_i, b_i] across the O(log N) canonical nodes covering their endpoints solves Klee's measure problem (computing the union area of N axis-aligned rectangles via plane sweep) in O(N log N) time.

In computational genomics, segment trees and interval trees (built on AVL trees or B-trees in tools such as bedtools and cgranges) index millions of genomic features—including exons, ChIP-seq peaks, and copy-number variants—to evaluate per-base coverage depth and interval intersection queries in O(log N + k) time. In string indexing, pairing a suffix array and its Longest Common Prefix (LCP) array with a Range Minimum Query segment tree computes the longest common prefix of any two suffixes in O(log n) time.

Why does a recursive segment tree allocate 4n array entries when it only has 2n − 1 nodes?

When n is not a power of two (such as n = 2^k + 1), recursive midpoint splitting pushes the deepest leaves to depth ⌈log₂ n⌉ + 1. In a 1-indexed binary heap layout (children at 2u and 2u + 1), a binary tree of height ⌈log₂ n⌉ requires up to 2 · 2^{⌈log₂ n⌉} − 1 < 4n slots because shallower leaves leave unused index gaps at the bottom level. An iterative bottom-up segment tree (or Euler-tour preorder node indexing) eliminates all gaps and uses 2n − 1 entries.

When should a Fenwick tree be chosen over a segment tree?

When operations are restricted to point updates and invertible range sum queries, a Fenwick tree requires n words of memory (one-quarter of a 4n recursive segment tree) and executes simple bitwise loops with lower instruction overhead. A segment tree is required whenever the aggregation operator lacks an inverse (such as dynamic Range Minimum/Maximum Query) or requires general lazy range transformations.

1. Bentley, J. L. (1977). Solutions to Klee's rectangle problems (Technical Report). Carnegie Mellon University, Department of Computer Science. https://doi.org/10.1184/R1/6607706.v1
2. Vaishnavi, V. K. (1982). "Computing point enclosures." IEEE Transactions on Computers, C-31(1), 22–29. https://doi.org/10.1109/TC.1982.1675882
3. Chazelle, B. (1988). "A functional approach to data structures and its use in multidimensional searching." SIAM Journal on Computing, 17(3), 427–462. https://doi.org/10.1137/0217026
4. Bender, M. A., & Farach-Colton, M. (2000). "The LCA problem revisited." Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN), LNCS 1776, 88–94. https://doi.org/10.1007/10719839_9
5. Li, H. (2019). "Cgranges: A fast C library for genomic range queries." Bioinformatics (arXiv:1912.02821 / bedtools & minimap2 interval engine). https://doi.org/10.48550/arXiv.1912.02821