What is a segment tree?

A segment tree is a binary tree built over an array where every node stores an aggregate of a contiguous interval: the leaves are the array elements and each internal node holds the combination (for example the sum) of its two children. It answers range queries and point updates on the array, each in O(log n) time.

Why is a segment tree range query O(log n)?

Any query range can be decomposed into at most about 2 log n precomputed node intervals. The query walks down from the root, taking a whole node whenever its interval lies fully inside the query and recursing only where the range partially overlaps, so it touches only a logarithmic number of nodes rather than every element.

How does a segment tree handle updates?

To update one element, you change its leaf and then walk up to the root, recomputing each ancestor from its children. Only the ancestors of that leaf change, and there are about log n of them, so a point update is O(log n) — the advantage over a prefix-sum array, where a single update invalidates O(n) prefixes.

Segment tree vs prefix sum vs Fenwick tree?

A prefix-sum array gives O(1) range-sum queries but O(n) updates, so it is best for immutable data. A Fenwick (binary indexed) tree gives O(log n) sum queries and updates with very little code and memory. A segment tree is the most general: O(log n) queries and updates for many associative operations (sum, min, max, gcd) and supports range updates with lazy propagation.

Algorithm · Data Structures

Ranges in Log Time.

Don't memorize the segment tree — watch it answer ranges in log time. Prefix sums give O(1) range queries but choke on updates. A segment tree fixes that: each node stores the sum of an interval, so a range query combines just a handful of covering nodes in O(log n) — and changing one value fixes a single leaf and ripples up to the root, also O(log n).

interval sums · range query · point update · O(log n)

NODE = INTERVAL

Every node stores the sum of a contiguous slice of the array.

LEAVES

The array elements themselves — the base of the tree.

QUERY

Combine the few nodes that fully cover the range — O(log n).

UPDATE

Change a leaf, recompute its ancestors up to the root — O(log n).

segment-tree.sim — array [2,1,5,3] · build · query · update

Ready

Leaves hold the array [2,1,5,3]; each parent stores the sum of its interval. Press Step to build the tree bottom-up, then answer a range query, then update a value and watch it ripple to the root.

Build

Phase

—

Result

Precompute the pieces, combine on demand

A prefix-sum array is unbeatable for range sums until a value changes — then every prefix after it is wrong, an O(n) repair. The segment tree trades that O(1) query for a still-fast O(log n) query in exchange for O(log n) updates, by storing partial sums at many granularities. No single node covers your exact range, but a logarithmic number of them tile it perfectly, and any single element sits under only a logarithmic number of nodes.

Build bottom-up

Leaves are the elements; each internal node is the sum of its two children. Building the whole tree is O(n).

Query a range

Walk down from the root: take a whole node if its interval lies inside the query, recurse where it partially overlaps. About 2 log n nodes.

Update a point

Change the leaf, then recompute each ancestor from its children up to the root — only log n nodes change.

Range updates

Lazy propagation defers pushing an update to children until needed, giving O(log n) range updates too.

Build

O(n)

Range query

O(log n)

Point update

O(log n)

Space

O(n)

The same tree works for any associative combine — swap sum for min, max, or gcd and you get range-min or range-gcd queries for free. Lighter alternatives exist: a Fenwick (binary indexed) tree does range-sum with updates in a few lines and less memory, while a prefix-sum array wins only when the data never changes.

Check yourself

1 · What does each internal node of a segment tree store?

Internal nodes hold the combination of their children, so they summarize a whole interval of the array.

2 · Why can a segment tree update a value in O(log n)?

A single element sits under a logarithmic number of nodes, so only those ancestors need recomputing.

3 · Compared to a prefix-sum array, a segment tree is better when…

Prefix sums give O(1) queries but O(n) updates; the segment tree keeps updates fast (O(log n)) for mutable data.

Questions

How much memory does a segment tree use?

About 2n to 4n nodes for an array of n elements (a common safe allocation is 4n). Each node stores one aggregate value, so it is O(n) space overall.

What is lazy propagation?

A technique for range updates: instead of updating every affected leaf, you mark a node as "pending +x for my whole interval" and only push that down to children when a later query or update needs to descend. It keeps range updates at O(log n).

When would I pick a Fenwick tree instead?

When you only need prefix or range sums with point updates, a Fenwick (binary indexed) tree is shorter to write and uses less memory. Reach for a segment tree when you need range updates, non-sum operations, or more flexibility.

Both ways, in log time.

Store interval sums in a tree and range queries and point updates both cost O(log n). The mutable cousin of the prefix sum.

← All algorithms Prefix Sums → Binary Search Tree → Big-O Cheatsheet →

Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Ranges in Log Time.

Precompute the pieces, combine on demand

Build bottom-up

Query a range

Update a point

Range updates

Check yourself

Questions

Both ways, in log time.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Precompute the pieces, combine on demand

Build bottom-up

Query a range

Update a point

Range updates

Check yourself

Questions

Both ways, in log time.

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.