Home▸Algorithms & AI▸Segment Tree — Range Sum & Range Minimum Queries

🌲 Segment Tree — Range Sum & Range Minimum Queries

Build a segment tree over an array in O(n) and answer range-sum or range-min queries and point updates in O(log n). Click a range to see which O(log n) nodes get combined.

Algorithms & AI2DAdvanced60 FPS

About Segment Tree — Range Sum & Range Minimum Queries

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.

⚙ Under the hood

Build a segment tree over an array in O(n) and answer range-sum or range-min queries and point updates in O(log n). Click a range to see which O(log n) nodes get combined.

data structurerange querytreedivide and conquer

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install