Segment Tree Introduction
A segment tree stores information about intervals of an array. It supports two operations efficiently: update one element, and query an aggregate value over a contiguous range. In this introduction, the aggregate is sum, so the operations are update(idx, value) — set arr[idx] = value — and query(left, right) — return arr[left] + arr[left + 1] + ... + arr[right]. Throughout this article, [left, right] means the inclusive range: both endpoints count.
The key constraint is that updates and range queries are interleaved. An update can change any index idx, not just the end of the array. A query can ask for any interval [left, right]. We want both operations to be much faster than scanning or rebuilding the whole array.
Why not the plain array?
Store the values in an array. Updating one index is O(1) — one write. But query(left, right) walks every element between left and right, so each range query costs O(n). With 1,000,000 elements and a range covering half of them, that is 500,000 additions per query.
Why not a prefix-sum array?
Precompute prefix[i] = arr[0] + arr[1] + ... + arr[i-1], the sum of the first i elements. Now query(left, right) = prefix[right + 1] - prefix[left] in O(1). But when arr[idx] changes, every prefix[i] with i > idx is stale. Rebuilding them costs O(n) per update. The prefix array bought cheap queries by making updates expensive.
Both structures optimize one side. A plain array is cheap to update and slow to query; a prefix-sum array is cheap to query and slow to update. We want both operations cheap on the same structure.
Caching sums on nested intervals
The reason query(left, right) is slow on the plain array is that we recompute the sum from scratch every time. If we had already cached the sum of arr[0..3] and the sum of arr[4..7], the query query(0, 7) would be one addition. The trick is to choose which intervals to cache so that any query can be covered by a few of them — and so that any update invalidates only a few of them.
Start with the whole array as one interval. Split it in half and cache the sum of each half. Split each half in half again and cache those. Continue until each interval holds a single element. Every cached interval is the union of its two children, so its sum is the sum of its children's sums — the caching is self-consistent.
This nested split is a binary tree. The root represents the full array. Each internal node represents an interval and stores its sum; its two children represent the left and right halves. Leaves represent single indices. In the diagram below, every node is labeled [i, j] — the index range it covers.
The height of the tree is ⌈log₂ n⌉, because each split halves the interval. That height is the budget for every operation below.
Range query
To compute query(query_left, query_right), we start at the root and recursively walk the tree, comparing each node's interval against the query interval. At every node we visit, exactly one of three cases applies.
When the node's interval sits entirely outside the query — the two intervals share no index — the node contributes 0 and we stop descending. When the node's interval sits entirely inside the query — every index the node covers is also in the query — we return its cached sum directly, without visiting anything below it. When the two intervals partially overlap — they share some indices but the node also covers indices the query does not want — we cannot use the cached sum as-is, so we recurse into both children and add their results.
The second case is the payoff. Once a node is fully inside the query, an entire subtree — potentially half the array — collapses to one lookup. Partial overlap is what keeps the recursion going, and it can only happen at nodes whose interval straddles one of the query's two endpoints. At each level of the tree there are at most two such nodes (one per endpoint), so the recursion visits a bounded number of nodes per level: O(log n) nodes in total.
Step through a query below: press Next to advance one node at a time, or Play to auto-run. Watch how each visited node lands in one of the three cases, and how the gray subtrees are never touched.
Point update
Updating a single index follows one root-to-leaf path. Start at the root; at each node, recurse into whichever child contains idx — the left child if idx ≤ mid, otherwise the right child. When we reach the leaf for idx, write the new value. On the way back up, every parent on that path recomputes its sum from its two children: tree[parent] = tree[left_child] + tree[right_child]. Nodes off the path are untouched — their cached sums are still correct. One path, O(log n) nodes updated.
Step through it below with Next. The walkthrough shows both phases — the descent choosing a child at each node, then the recomputation as the recursion unwinds. It also shows the flat tree array the implementation section introduces, so you can see how tree positions map to array slots. The third preset steps through building the whole tree from scratch.
Implementation
Laying the tree out as a flat array
Allocating a real tree of pointer nodes works, but there is a simpler layout: put the tree inside a flat array tree[] using the indexing familiar from binary heaps. The root sits at index 1. For a node at index cur, its left child sits at 2 * cur and its right child at 2 * cur + 1; going the other direction, the parent of node i sits at i / 2 (integer division). Starting the root at 1 instead of 0 is what makes this arithmetic clean — with a 0-based root the children would sit at 2 * cur + 1 and 2 * cur + 2.
Two arrays are in play, and keeping them separate in your head matters. The input array arr stays 0-indexed and holds the actual values. The tree array tree is 1-indexed and holds one cached sum per node. A node's position in tree[] is pure bookkeeping; what the node means is the interval [cur_left, cur_right] of arr that it covers.
For arr = [2, 1, 5, 3], the tree has seven nodes and they land in tree[1..7]: tree[1] caches the sum of [0, 3] (the whole array), tree[2] and tree[3] cache the sums of the halves [0, 1] and [2, 3], and tree[4] through tree[7] cache the four single elements.
How big must tree[] be? A segment tree over n elements has n leaves and n - 1 internal nodes — 2n - 1 nodes total. When n is a power of two, the tree is perfectly balanced and those nodes pack into tree[1..2n-1] with no gaps. When n is not a power of two, the bottom level is ragged, and heap indexing assigns slots by position in a full tree rather than packing nodes tightly — so some slots go unused and leaf indices can reach beyond 2n. The worst case needs 2 * next_power_of_two(n) slots, and since next_power_of_two(n) is less than 2n, allocating 4 * n is always enough. That is why implementations reach for 4n: it wastes some memory to avoid computing powers of two, and it never overflows.
The recursive functions
Both operations are recursive functions that walk this flat array. Each call carries three pieces of state describing where we are: cur (the index of the current node in tree[]), and cur_left, cur_right (the interval of arr that this node covers). The caller always starts at the root, so the first call passes cur = 1, cur_left = 0, cur_right = n - 1. As the recursion descends, these three values update in lockstep: moving to the left child means cur * 2 covering [cur_left, cur_mid], and moving to the right child means cur * 2 + 1 covering [cur_mid + 1, cur_right], where cur_mid = (cur_left + cur_right) / 2 rounded down. The point-update walkthrough above shows these three values changing at each step, alongside the flat tree array.
How update works
update(cur, cur_left, cur_right, idx, val) sets arr[idx] = val in the tree. Beyond the three where-we-are parameters, it takes the job to do: which index changes and its new value.
The base case is cur_left == cur_right. The node covers exactly one index — and since the recursion only ever descends toward idx, that index is idx — so we write tree[cur] = val and return. Otherwise the node has two children split at cur_mid. Only one of them contains idx: if idx <= cur_mid it lies in the left child's interval, otherwise in the right child's. We recurse into that child and leave the other alone. After the recursive call returns, everything below the current node is correct, and one assignment repairs the current node itself: tree[cur] = tree[cur * 2] + tree[cur * 2 + 1]. Because this line runs while the recursion unwinds, parents recompute bottom-up, each one reading two children that are already up to date.
How query works
query(cur, cur_left, cur_right, query_left, query_right) returns the sum of the values in [query_left, query_right], restricted to the part of the array this node covers. The three cases from the range-query section map one-to-one onto the three returns in the code.
The first check catches "entirely outside": cur_left > query_right or cur_right < query_left means the node's interval and the query share no index, so the node contributes 0 — the neutral element for sum, safe to add without changing the result. The second check catches "entirely inside": query_left <= cur_left and cur_right <= query_right means every value under this node is wanted, so the cached tree[cur] is exactly the subtree's contribution and we return it without recursing. If neither check fires, the intervals partially overlap, and the final lines recurse into both children and add the two results. Any index the query wants is counted exactly once (leaves partition the array), and any index outside the query falls into some "entirely outside" subtree that contributes 0.
Building the tree
The constructor allocates tree as 4n zeros, then inserts the input values one at a time: for each index i, it calls update(1, 0, n - 1, i, arr[i]). Each call pushes one value down to its leaf and refreshes the sums along that root-to-leaf path, so after the loop finishes, every node holds the true sum of its interval. The "Build from scratch" preset in the point-update walkthrough above steps through exactly this loop, insert by insert. The n inserts cost O(log n) each, so the build totals O(n log n). A dedicated bottom-up build — fill in the n leaves first, then compute each parent from its two children — runs in O(n), but reusing update keeps the code shorter, and the build runs only once.
1class SegmentTree:
2 def __init__(self, arr):
3 # 4n is a safe upper bound for the flat tree array
4 self.tree = [0] * (4 * len(arr))
5 for i in range(len(arr)):
6 self.update(1, 0, len(arr) - 1, i, arr[i])
7
8 # walk down to the leaf for idx, then recompute sums on the way up
9 def update(self, cur, cur_left, cur_right, idx, val):
10 if cur_left == cur_right:
11 self.tree[cur] = val
12 return
13 cur_mid = (cur_left + cur_right) // 2
14 if idx <= cur_mid:
15 self.update(cur * 2, cur_left, cur_mid, idx, val)
16 else:
17 self.update(cur * 2 + 1, cur_mid + 1, cur_right, idx, val)
18 self.tree[cur] = self.tree[cur * 2] + self.tree[cur * 2 + 1]
19
20 # sum of arr[query_left..query_right]
21 def query(self, cur, cur_left, cur_right, query_left, query_right):
22 # current interval sits entirely outside the query
23 if cur_left > query_right or cur_right < query_left:
24 return 0
25 # current interval sits entirely inside the query
26 if query_left <= cur_left and cur_right <= query_right:
27 return self.tree[cur]
28 # partial overlap: recurse into both children
29 cur_mid = (cur_left + cur_right) // 2
30 return (self.query(cur * 2, cur_left, cur_mid, query_left, query_right)
31 + self.query(cur * 2 + 1, cur_mid + 1, cur_right, query_left, query_right))
321public static class SegmentTree {
2 int[] tree;
3
4 public SegmentTree(int[] arr) {
5 // 4n is a safe upper bound for the flat tree array
6 tree = new int[4 * arr.length];
7 for (int i = 0; i < arr.length; i++) {
8 update(1, 0, arr.length - 1, i, arr[i]);
9 }
10 }
11
12 // walk down to the leaf for idx, then recompute sums on the way up
13 void update(int cur, int curLeft, int curRight, int idx, int val) {
14 if (curLeft == curRight) {
15 tree[cur] = val;
16 return;
17 }
18 int curMid = (curLeft + curRight) / 2;
19 if (idx <= curMid) update(cur * 2, curLeft, curMid, idx, val);
20 else update(cur * 2 + 1, curMid + 1, curRight, idx, val);
21 tree[cur] = tree[cur * 2] + tree[cur * 2 + 1];
22 }
23
24 // sum of arr[queryLeft..queryRight]
25 int query(int cur, int curLeft, int curRight, int queryLeft, int queryRight) {
26 // current interval sits entirely outside the query
27 if (curLeft > queryRight || curRight < queryLeft) return 0;
28 // current interval sits entirely inside the query
29 if (queryLeft <= curLeft && curRight <= queryRight) return tree[cur];
30 // partial overlap: recurse into both children
31 int curMid = (curLeft + curRight) / 2;
32 return query(cur * 2, curLeft, curMid, queryLeft, queryRight)
33 + query(cur * 2 + 1, curMid + 1, curRight, queryLeft, queryRight);
34 }
35}
361class SegmentTree {
2 constructor(arr) {
3 // 4n is a safe upper bound for the flat tree array
4 this.tree = Array(4 * arr.length).fill(0);
5 for (let i = 0; i < arr.length; i++) {
6 this.update(1, 0, arr.length - 1, i, arr[i]);
7 }
8 }
9
10 // walk down to the leaf for idx, then recompute sums on the way up
11 update(cur, curLeft, curRight, idx, val) {
12 if (curLeft === curRight) {
13 this.tree[cur] = val;
14 return;
15 }
16 const curMid = Math.floor((curLeft + curRight) / 2);
17 if (idx <= curMid) {
18 this.update(cur * 2, curLeft, curMid, idx, val);
19 } else {
20 this.update(cur * 2 + 1, curMid + 1, curRight, idx, val);
21 }
22 this.tree[cur] = this.tree[cur * 2] + this.tree[cur * 2 + 1];
23 }
24
25 // sum of arr[queryLeft..queryRight]
26 query(cur, curLeft, curRight, queryLeft, queryRight) {
27 // current interval sits entirely outside the query
28 if (curLeft > queryRight || curRight < queryLeft) return 0;
29 // current interval sits entirely inside the query
30 if (queryLeft <= curLeft && curRight <= queryRight) return this.tree[cur];
31 // partial overlap: recurse into both children
32 const curMid = Math.floor((curLeft + curRight) / 2);
33 return this.query(cur * 2, curLeft, curMid, queryLeft, queryRight)
34 + this.query(cur * 2 + 1, curMid + 1, curRight, queryLeft, queryRight);
35 }
36}
371struct SegmentTree {
2 std::vector<int> tree;
3
4 SegmentTree(const std::vector<int>& arr) : tree(4 * arr.size(), 0) {
5 // 4n is a safe upper bound for the flat tree array
6 for (int i = 0; i < (int)arr.size(); i++) {
7 update(1, 0, arr.size() - 1, i, arr[i]);
8 }
9 }
10
11 // walk down to the leaf for idx, then recompute sums on the way up
12 void update(int cur, int cur_left, int cur_right, int idx, int val) {
13 if (cur_left == cur_right) {
14 tree[cur] = val;
15 return;
16 }
17 int cur_mid = (cur_left + cur_right) / 2;
18 if (idx <= cur_mid) update(cur * 2, cur_left, cur_mid, idx, val);
19 else update(cur * 2 + 1, cur_mid + 1, cur_right, idx, val);
20 tree[cur] = tree[cur * 2] + tree[cur * 2 + 1];
21 }
22
23 // sum of arr[query_left..query_right]
24 int query(int cur, int cur_left, int cur_right, int query_left, int query_right) {
25 // current interval sits entirely outside the query
26 if (cur_left > query_right || cur_right < query_left) return 0;
27 // current interval sits entirely inside the query
28 if (query_left <= cur_left && cur_right <= query_right) return tree[cur];
29 // partial overlap: recurse into both children
30 int cur_mid = (cur_left + cur_right) / 2;
31 return query(cur * 2, cur_left, cur_mid, query_left, query_right)
32 + query(cur * 2 + 1, cur_mid + 1, cur_right, query_left, query_right);
33 }
34};
35Tracing the running example
The two walkthroughs above run on arr = [2, 1, 5, 3], indices 0..3, and their captions narrate every step. In widget terms, query(1, 3) is the full entry call query(1, 0, 3, 1, 3) — start at the root node 1, which covers [0, 3], and ask for the interval [1, 3] — and update(2, 0) stands for update(1, 0, 3, 2, 0).
Two results are worth confirming as you step through them. query(1, 3) visits the root (partial overlap), descends left to reach [1, 1] (returns 1) while [0, 0] falls outside (returns 0), and takes [2, 3] whole from its cached sum 8; the total is 0 + 1 + 8 = 9, matching arr[1] + arr[2] + arr[3]. Then update(2, 0) walks the single path root → [2, 3] → [2, 2], writes 0, and recomputes [2, 3] to 3 and the root to 6, leaving the untouched [0, 1] subtree alone. A follow-up query(1, 3) then returns 1 + 3 = 4, reflecting the update.
What about performance?
Both query and update run in O(log n) because each operation visits a bounded number of nodes per level, and the tree has ⌈log₂ n⌉ levels. For update, each level visits exactly one node — the one on the root-to-leaf path for idx. For query, each level visits at most four nodes: the two that span the query boundaries plus their immediate siblings. Everything else collapses into a single cached read.
Space is O(n). The flat tree array of size 4n is an over-allocation for simplicity; the tree itself holds fewer than 2n useful entries.
For the interview
Reach for a segment tree when a problem mixes frequent range queries and frequent point updates, and either a plain array or a prefix-sum array leaves one side slow. Signals in the problem statement: "sum / min / max / gcd over a range," "after each update," or queries interleaved with updates.
The operation does not have to be sum. Any associative operation with a neutral element works — min, max, gcd, bitwise OR. Change the merge rule (tree[parent] = left + right becomes tree[parent] = min(left, right), and so on) and the "outside the query" return value (0 for sum, +∞ for min), and the same structure answers a different question. Range Maximum Query, the next article in this section, applies exactly this swap.
The implementation has many interval boundary cases, so off-by-one mistakes are easy. In an interview, explaining when to reach for a segment tree and how query and update decompose the range is often enough to move forward; you can then fill in the code with care. Range updates with lazy propagation are a follow-up topic layered on the same shape.