📏 Segment Tree
Range queries in O(log n)
Mode
Query [L, R]
Point update
Stats
Array size
0
Nodes visited
0
Query result
—
Mode
Sum
Info & Theory

A segment tree is a binary tree built over the indices of an array, where each node covers a contiguous range. Leaves cover single elements; each internal node stores an aggregate (sum or minimum) of its range, computed from its two children.

O(n) build

Building bottom-up (or via a recursive divide-and-conquer) combines n leaves into ~2n total nodes, doing O(1) work per node — O(n) overall.

O(log n) range query

A query [L,R] recurses into a node's range: if it's fully outside [L,R], skip; if fully inside, use the node's precomputed aggregate directly; if partially overlapping, recurse into both children. At most O(log n) nodes are ever fully combined, because the query range decomposes into at most two "chains" of canonical sub-ranges per tree level.

O(log n) point update

Updating one array element only invalidates the O(log n) ancestors on the path from that leaf to the root; each is recomputed from its two children on the way back up.

Why not just prefix sums?

Prefix sums answer range-sum in O(1) but need O(n) to update a single element, and cannot support range-minimum at all (minimum has no inverse operation). A segment tree trades a little query speed for fast updates and support for any associative combiner.

Beyond this simulation

Lazy propagation extends segment trees to support O(log n) range updates (not just point updates) by deferring pending updates on subtrees until they are actually visited.

About Segment Tree — Range Sum & Range Minimum Queries

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 11 July 2026

A segment tree is a binary tree built over the indices of an array in which each node represents a contiguous range and stores an aggregate value — a sum, minimum, maximum, or any other associative combination — of that range, computed from its two children. Construction takes O(n) time and roughly 2n to 4n nodes for an array of n elements. A range query over [L, R] recursively descends the tree, immediately using a node's precomputed aggregate whenever its range lies entirely inside [L, R], skipping ranges entirely outside it, and recursing into children only for partial overlaps; this touches at most O(log n) nodes because the query decomposes into a bounded number of canonical sub-ranges per level. A point update only needs to recompute the O(log n) ancestors on the path from the modified leaf to the root. Compared with prefix sums, which answer range-sum in O(1) but require O(n) to update an element and cannot support range-minimum at all, a segment tree trades a small constant-factor query cost for O(log n) updates and support for any associative operator.

Frequently Asked Questions

Why does a segment tree query only touch O(log n) nodes?

Any query range [L, R] can be decomposed into at most O(log n) "canonical" node ranges — at each level of recursion, the query boundary can split at most two nodes into partial overlaps, while everything strictly between those boundaries is either fully included or fully excluded. Summing this bounded work across the tree's O(log n) levels gives the overall O(log n) query cost.

Why use a segment tree instead of prefix sums for range queries?

Prefix sums answer a range-sum query in O(1) but require O(n) work to update a single array element, since every prefix sum after that index must shift. Prefix sums also cannot answer range-minimum queries at all, because subtraction has no analog for minimum. A segment tree supports both point updates and range queries — for any associative operator — in O(log n).

How does a point update propagate through the tree?

Updating the array at one index changes exactly one leaf. The update then walks upward along the unique path from that leaf to the root, recomputing each ancestor's aggregate as the combination of its two children's current values. Since the tree has height O(log n), this touches O(log n) nodes total.

How much memory does a segment tree use?

A recursive or array-based segment tree over n elements typically uses between 2n and 4n nodes, depending on implementation (a common array-based layout allocates 4n slots to safely accommodate non-power-of-two sizes without careful indexing). This is a constant-factor overhead compared with the O(n) input array, which is a small price for O(log n) queries and updates.