Segment Tree: Fast Range Queries with Updates

Given an array, you must answer many questions like "what is the sum of elements from index l to r" while values also change. A plain loop answers a query in O(n). A prefix-sum array answers queries in O(1) but one change forces O(n) rebuilding. When queries and updates are mixed, both approaches get slow.

Think of a leaderboard of 100,000 players whose scores change every few seconds while a page keeps asking for the total of ranks 200 to 5,000.

A segment tree balances the two. Query and update both cost O(log n), and for 100,000 items log2 n is about 17. Reads get slightly slower than with prefix sums. Writes get far faster.

Picture a binary tree. The leaves are the array elements. Each parent stores the combined value (here the sum) of its two children, so the root holds the sum of everything. A query for a range is answered by combining a small number of nodes whose ranges exactly cover it. An update changes one leaf and fixes the sums on the path up to the root.

A tree over n items has about 2n nodes. The array form stores them in a list of size 2n: leaves at positions n to 2n-1, and node i has children 2i and 2i+1.

Take a = [5, 8, 6, 3, 2, 7, 2, 6]; the diagram labels each node with its index and the half-open range it sums. Now trace query(1, 7), the sum of a[1] through a[6]. Shift both ends by n, giving l = 9 and r = 15.

At the leaves, l = 9 is odd, so t[9] is a right child whose parent also covers a[0], outside the range. Take t[9] = 8 and move l to 10. r = 15 is odd too, so step r back to 14 and take t[14] = 2. Halve both: l = 5, r = 7.

One level up, t[5] = 9 (a[2] + a[3]) and t[6] = 9 (a[4] + a[5]) are taken the same way. Halving gives l = r = 3, and the loop ends.

The answer is 8 + 2 + 9 + 9 = 28, built from four nodes instead of six values. At most two nodes are taken per level, and there are about log2 n levels, so the saving grows with the array.

The range is half-open, like Python slices: query(l, r) covers l up to but not including r. In the loop, a node at an odd position is a right child, which means its parent would include something outside the range, so we take it directly and move on. The right end mirrors it.

update(i, value) writes the leaf at i + n, then halves the index up to the root, recomputing each parent from its two children.

Building touches each internal node once, so it is O(n). A query takes at most two nodes per level and an update walks one path, so each is O(log n). Memory is O(n).

For [2, 1, 5, 3, 4], query(1, 4) covers 1, 5 and 3, and returns 9. After update(2, 10), the same query covers 1, 10 and 3 and returns 14.

On 1,000 random numbers I then ran 5,000 random operations, about half of them updates, and compared every query with sum(a[l:r]) on a plain list. Not one answer differed. Testing a clever structure against an obviously correct slow one is the quickest way to trust it.

Next I timed four approaches on 100,000 random values with 10,000 operations, changing only the share of updates (Python 3.13, 4-core sandbox, best of three, build time included):

Prefix sums win when nothing changes and collapse when half the operations are updates, since each update rebuilds 100,001 entries. The naive loop is slow throughout. The segment tree stayed near 0.04 s for every mix, and that flat column is the point.

The Fenwick column looks worse than it is. My Fenwick build calls add once per element, which is O(n log n) and took 0.120 s against 0.012 s for the segment tree. An O(n) build exists (each entry i adds itself into entry i + (i & -i)); in a separate run it built the same array in 0.013 s against 0.116 s for the add loop. With both built in advance, the operations took 0.025 to 0.031 s on Fenwick and 0.033 to 0.035 s on the segment tree. Your absolute times will differ.

Suppose each update says "add 10 to every element from index 2 to 5" and queries still ask for range sums. As separate point updates that costs O(k log n) for k elements.

Lazy propagation is deliberately late. When an update fully covers a node's range, the tree adds v times the range length to that node's sum, records v in a pending tag, and stops. Only when a later operation must pass through that node is the tag pushed down one level: each child receives the add, and the parent's tag resets to 0.

On the diagram's array, adding 10 to [2, 6) tagged exactly two nodes, t[5] and t[6], each going from 9 to 29, and the root rose from 39 to 79. A later query(3, 5) pushed the tags down on its way and returned 25.

Pushing needs each node's range, so lazy trees are usually written recursively from the root. On 5,000 random range adds and range sums over 1,000 values, every query matched brute force. Both operations stay O(log n). Push before you descend; recompute the parent after you return.

A Fenwick tree, also called a binary indexed tree, keeps partial sums in one array of n + 1 entries. Entry i covers a block whose length is the lowest set bit of i, so both prefix(i) and add(i, delta) walk about log2 n steps using i & -i. A range sum is prefix(r) - prefix(l).

That subtraction is the catch. It works for sums, XOR and anything else with an inverse. Minimum and maximum have none: knowing min(a[0:7]) and min(a[0:2]) tells you nothing about min(a[2:7]). A segment tree combines disjoint pieces directly, so min, max or gcd only change the combine line and the identity value (0 for sum, infinity for min).

• Prefix sums with point updates, short code: Fenwick tree.
• Min, max, gcd or a custom merge: segment tree.
• Range adds with range sums: segment tree with lazy propagation.
• No updates: plain prefix sums, the fastest option in the benchmark's first row.

Array size for the recursive tree. In it, node 1 covers [0, n) and each node splits at the midpoint. When n is not a power of two the tree is uneven, and the largest index can approach 4n. Checking every n from 1 to 5,000, the worst was n = 4,097, whose deepest node sat at index 16,383. Allocating 2n there fails, so allocate 4n. The bottom-up layout fits in exactly 2n.

Off-by-one ranges. This code uses half-open ranges; many textbooks use closed [l, r]. Mixing the two drops the last element or adds a neighbour. Pick one, comment it, and test a range of length one.

Order in the bottom-up query. The loop adds edge pieces into one total as it meets them. Addition does not care; concatenation does. Over the letters "abcdefgh", query(1, 7) returned "bgcdef" instead of "bcdefg". The fix is two accumulators, left = left + t[l] and right = t[r] + right, joined at the end. With it, all 35,990 non-empty ranges over arrays of 1 to 59 elements matched.

Q: What problem does a segment tree solve?
A: Range queries such as sum, min or max on an array that also changes, with both operations in O(log n).

Q: Why not a prefix-sum array?
A: Queries are O(1) but each update costs O(n) to rebuild. With 4,973 updates among 10,000 operations on 100,000 values, prefix sums took 14.579 s against 0.041 s for the segment tree.

Q: Walk me through a range query.
A: Shift l and r to leaves. While l < r, an odd l is taken and stepped right, an odd r is stepped left and taken, then both halve. On [5, 8, 6, 3, 2, 7, 2, 6], query(1, 7) adds four nodes for 28.

Q: How much memory does it need, and why do people say 4n?
A: O(n). Bottom-up uses 2n slots. The recursive version can index up to almost 4n, as with n = 4,097 reaching index 16,383.

Q: What is lazy propagation?
A: A fully covered node gets its sum adjusted and a pending tag; children are updated only when a later operation passes through. Both operations stay O(log n).

Q: Segment tree or Fenwick tree?
A: Fenwick for prefix sums with point updates: less code, n + 1 slots. Segment tree for min or max, custom merges, or lazy range updates.