Overview
A segment tree recursively partitions an array into intervals and stores an aggregate for each interval. Queries combine summaries from O(log n) disjoint nodes, and updates repair summaries on the path to the root.
CoreSource checked
Segment Tree
Maintains aggregate values over intervals by storing summaries in a binary tree.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Intermediate
- Family
- Range Query Tree
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
range partitiontree aggregatepoint updaterange querystored invariantrange aggregatetree structurerange query tree
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(log n)
Worst
O(log n)
Space
O(n)
When to Use
- Use when range queries and updates must both be efficient.
- Use when the aggregate is associative and interval structure matters.
When Not to Use
- Avoid when static prefix sums or sparse tables solve the problem more simply.
- Avoid when memory overhead or implementation complexity is not justified.
What It Does
- Partitions an indexed range into tree intervals
- Stores an aggregate for each interval
- Answers range queries by combining covered nodes
Use Cases
- Range minimum, maximum, sum, or gcd queries
- Point updates with range queries
- Lazy range updates when extended with propagation
Inputs
- Array
- Associative combine operation
Outputs
- Range query answers
Pseudocode
- 1.Build leaves from array values
- 2.Build each internal node by combining its children
- 3.For a query, return identity on no overlap
- 4.Return the node aggregate on full cover
- 5.Otherwise combine answers from left and right children
Canonical Example
- Input
- array [2, 7, 1, 5], query min on indexes 1..3
- Output
- 1
- Explanation
- The query combines tree nodes covering the requested range and returns the minimum.
Implementation Notes
- Define intervals as half-open or inclusive and use that convention everywhere.
- Test single-element, empty-overlap, and full-cover queries.
- Keep combine, identity, and update behavior configurable but explicit.
Common Pitfalls
- Wrong interval inclusivity causes off-by-one query bugs.
- Lazy propagation must be pushed before descending into stale children.
- The combine function must match the identity value.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow array intervals grouped into a tree of aggregates.
Step 1 of 5: Build leaves from array values
interval-tree-levelsNotes
Segment trees are flexible, but their correctness depends on consistent interval conventions.
Sources (1)
What each reference supports for this entry.
Handbook of Data Structures and Applications
BookData-structures reference for segment trees, interval aggregation, range queries, and update traversal.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsPersistent Segment Tree
Data Structures · Specialized
Persistent segment trees retain historical versions of segment tree updates.
Compare with thisAlternative toFenwick Tree
Data Structures · Core
Segment trees handle more general range queries and updates than Fenwick trees.
Compare with thisRelationships
View full relationship pageAlternative toFenwick Tree
Segment trees handle more general range queries and updates than Fenwick trees.
Alternative toSparse Table
Segment trees support updates, while sparse tables are usually static.
Related Algorithms
Tags
Data StructureRange QueryTree