Loading…

mediumTreesSometimes asked

Segment Tree for Range Sum

Q: How do you solve Segment Tree for Range Sum using the Baseline — Plain Array (Loop the Range) approach?

When to use it: Say this first: it is correct and trivial, and it makes the cost trade-off obvious before you reach for a tree. The simplest correct structure is the array itself. **Update is trivial.** Setting `a[i] = val` is one assignment, O(1). Nothing else to maintain. **Query is a loop.** To answer `rangeSum(l, r)` you add `a[l]` through `a[r]` directly — up to n additions in the worst case. **Why this is not enough.** The problem allows up to 10⁵ queries, each potentially spanning the whole array. That is up to 10¹⁰ additions — far beyond what runs in time. The opposite extreme, a prefix-sum array, flips the trade: queries become O(1) but every update forces you to rebuild the suffix of the prefix array, again O(n). Neither extreme is good when updates and queries are interleaved. **The lesson that points to the tree.** We want *both* operations sub-linear. The segment tree achieves O(log n) for each by storing partial sums at multiple granularities, so neither a query nor an update ever touches more than O(log n) of them. Time complexity: O(1) update, O(n) query. Space complexity: O(n).

Trees & BST · 29 of 41 · 11 min

Design a data structure over an integer array a[0..n-1] that supports two operations efficiently after building:

1
**rangeSum(l, r)** — return the sum of a[l] + a[l+1] + … + a[r].
2
**update(i, val)** — set a[i] = val.

The operations are interleaved and there can be up to 10⁵ of each. Build once, then answer every operation in **O(log n)**.

In plain English

We need a structure where neither operation degrades to O(n). The key realization: a sum over any range can be assembled from a small set of precomputed interval sums. A segment tree precomputes the sum of every 'canonical' interval (the whole array, each half, each quarter, …) so any query range is covered by O(log n) of them, and any single value change touches only O(log n) of them.

Examples

Example 1

Input: a = [1, 3, 5, 7, 9, 11]; rangeSum(1, 3)
Output: 15
Note: a[1] + a[2] + a[3] = 3 + 5 + 7 = 15.

Example 2

Input: a = [1, 3, 5, 7, 9, 11]; update(1, 10); rangeSum(1, 3)
Output: 22
Note: After a[1] becomes 10, the sum is 10 + 5 + 7 = 22.

Example 3

Input: a = [1, 3, 5, 7, 9, 11]; rangeSum(0, 5)
Output: 36
Note: The full-array sum is stored at the root, so this query returns in O(1) once the root is reached.

Constraints

1 ≤ n ≤ 10⁵
Up to 10⁵ mixed update and rangeSum calls
0 ≤ l ≤ r ≤ n − 1 for every query
Values fit in 64-bit after summation (use long in Java)

Clarifying questions4First question: Are updates point updates or range updates?Explore questions

Q1.Are updates point updates or range updates?
Point updates here (set one index). Range updates need lazy propagation, which is a layer on top of this same tree — worth mentioning as the follow-up.
Q2.Is the array static or changing?
Changing. If it were static, a prefix-sum array gives O(1) queries and no tree is needed — say that to show you reach for the simplest tool first.
Q3.What aggregate — sum, min, max?
Sum here, but the structure is identical for any associative merge. Only the combine step and the identity element change.
Q4.Could the recursion get deep enough to overflow the stack?
Depth is O(log n) ≈ 17 for n = 10⁵, so recursion is safe. For pedagogically deep structures you would switch to the iterative bottom-up segment tree, which I can mention.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

When you must both query a range sum and update single elements many times, a plain array forces one of the two operations to be O(n). A segment tree stores partial sums in a binary tree: each node owns a sub-interval and holds the sum of that interval. Build is O(n), a range-sum query is O(log n), and a point update is O(log n). Store the tree in a flat array of size about 4n; the children of node i sit at 2i and 2i+1.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that interleaved updates and range queries rule out prefix sums, and whether you can implement the three-way overlap logic (no overlap / total overlap / partial overlap) correctly.

Where candidates slip

Returning the wrong identity for the 'no overlap' case (e.g. returning a stored value instead of 0), or under-sizing the tree array to 2n and overflowing, or forgetting to re-sum ancestors after an update.

How to stand out

Start with the array baseline and state the O(n) cost of one operation, then explain that a range decomposes into O(log n) canonical nodes. Mention that swapping `+` for `min`/`max` reuses the entire structure.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Plain Array (Loop the Range)	`O(1) update, O(n) query`	`O(n)`	Say this first: it is correct and trivial, and it makes the cost trade-off obvious before you reach for a tree.	Read
2	Segment Tree — Recursive Array Implementation (Optimal)Optimal	`O(n) build, O(log n) query, O(log n) update`	`O(n)`	The answer they want once updates and queries are interleaved. 'Each node owns an interval and stores its sum; both operations walk O(log n) nodes.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Segment tree over [1,3,5,7]

How to read it:Each node stores the sum of its interval; the root holds the total. A query merges the few nodes that cover its range.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Plain Array (Loop the Range)

TimeO(1) update, O(n) querySpaceO(n)

Say this first: it is correct and trivial, and it makes the cost trade-off obvious before you reach for a tree.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Store the array as-is. update(i, val) is a single assignment — O(1).

2Hint 2Explore hint

rangeSum(l, r) loops from l to r adding each element — O(n) per query.

3Hint 3Explore hint

With up to 10⁵ queries each scanning up to 10⁵ elements, that is up to 10¹⁰ operations. Too slow — this motivates the tree.

A · Core idea

The simplest correct structure is the array itself.

Update is trivial. Setting a[i] = val is one assignment, O(1). Nothing else to maintain.

Query is a loop. To answer rangeSum(l, r) you add a[l] through a[r] directly — up to n additions in the worst case.

Why this is not enough. The problem allows up to 10⁵ queries, each potentially spanning the whole array. That is up to 10¹⁰ additions — far beyond what runs in time. The opposite extreme, a prefix-sum array, flips the trade: queries become O(1) but every update forces you to rebuild the suffix of the prefix array, again O(n). Neither extreme is good when updates and queries are interleaved.

The lesson that points to the tree. We want both operations sub-linear. The segment tree achieves O(log n) for each by storing partial sums at multiple granularities, so neither a query nor an update ever touches more than O(log n) of them.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 5, 7, 9, 11]; rangeSum(1, 3)

i=1

sum += 3

Statesum = 3

Final result15

C · Code with teaching comments

Reference implementation previewclass RangeArray { private final long[] a; RangeArray(int[] input) { a = new long[input.length];Explore the full code

solution.javaJava

Baseline — Plain Array (Loop the Range) — reference

2 teaching notes

1
class RangeArray {
2
    private final long[] a;
3
 
4
    RangeArray(int[] input) {
5
        a = new long[input.length];
6
        for (int i = 0; i < input.length; i++) {
7
            a[i] = input[i];
8
        }
9
    }
10
 
11
    void update(int i, int val) {
12
        // Point update is a single write — the cheap operation here.
13
        a[i] = val;            // O(1)
14
    }
15
 
16
    long rangeSum(int l, int r) {
17
        long sum = 0;
18
        // Scanning the range is the expensive operation that the tree will fix.
19
        for (int i = l; i <= r; i++) {  // O(n)
20
            sum += a[i];
21
        }
22
        return sum;
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(1) update, O(n) query timeO(n) spaceOpen the invariant and proofExplore the proof

The array baseline and the prefix-sum array are the two endpoints of a trade: one makes updates cheap and queries expensive, the other does the reverse. The segment tree sits in the middle, paying a logarithm for both — which is exactly what you want when neither operation is rare.

ComplexityO(1) update, O(n) query time, O(n) space — Update writes one cell (O(1)). A query sums up to n cells (O(n)). With q queries the total is O(q·n), which blows up when both q and n are large.

E · Edge cases and pitfalls3Using a prefix-sum array instead and forgetting that updates then cost O(n).Explore edge cases

Pitfalls

Using a prefix-sum array instead and forgetting that updates then cost O(n).
Assuming O(n) per query is fine — it is not when both n and the query count are ~10⁵.
Off-by-one on the inclusive r (loop to r, not r-1).

03.2

Approach 2 of 2 · Optimal

Segment Tree — Recursive Array Implementation (Optimal)

TimeO(n) build, O(log n) query, O(log n) updateSpaceO(n)

The answer they want once updates and queries are interleaved. 'Each node owns an interval and stores its sum; both operations walk O(log n) nodes.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build a binary tree where each node owns a contiguous sub-interval and stores the sum of that interval. The root owns [0, n-1].

2Hint 2Explore hint

For a query, classify each node three ways: its interval is fully outside the query (return 0), fully inside (return its stored sum), or partially overlapping (recurse into both children and add).

3Hint 3Explore hint

For an update, walk down to the single leaf for index i, set it, then re-sum each ancestor on the way back up. Store the tree in a flat array of size 4n; children of node v are 2v and 2v+1.

A · Core idea

A segment tree is a balanced binary tree laid over the array. The root represents the whole range [0, n-1]; each internal node splits its range at the midpoint into a left child [lo, mid] and a right child [mid+1, hi]; the leaves are the individual elements. Every node stores the sum of its own interval.

Why any query is O(log n). The central fact is that any sub-range [l, r] can be written as the disjoint union of O(log n) of these canonical intervals. When the query descends from the root, at each node one of three things happens: the node's interval is completely outside [l, r] (contribute the identity, 0, and stop), completely inside [l, r] (return the node's stored sum and stop — no need to go deeper), or it partially overlaps (recurse into both children and add the results). Only the partial-overlap nodes branch, and there are at most O(log n) of those along each side of the range, so the query touches O(log n) nodes total.

Why the identity matters. For a sum, the 'fully outside' case must contribute 0 — the additive identity — so it changes nothing. If the aggregate were min, the identity would be +∞; for max it would be −∞. Returning a stored value or the wrong identity here is the classic bug that silently corrupts answers.

Why any update is O(log n). Changing a[i] affects exactly the chain of nodes whose intervals contain i — that is one node per level, from the leaf up to the root, O(log n) of them. We set the leaf to the new value, then on the way back up recompute each parent as the sum of its two children. Every other node is untouched because its interval does not contain i.

Why build is O(n). Building fills each node's sum once in a post-order pass: a leaf copies its array element, an internal node adds its two children. There are about 2n nodes, so the build is linear.

Why a flat array of size 4n. Storing the tree implicitly (node v has children 2v and 2v+1, starting the root at index 1) avoids pointers entirely. When n is not a power of two the recursion can reach indices up to slightly below 4n, so 4n is the safe allocation that never overflows.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 5, 7]; build, then rangeSum(1, 3), then update(1, 10), rangeSum(1, 3)

Array state

after build

tree[1]=16 (root), tree[2]=4, tree[3]=12, tree[4..7]=1,3,5,7

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final result15 then 22

C · Code with teaching comments

solution.javaJava

Segment Tree — Recursive Array Implementation (Optimal) — optimal

5 teaching notes

1
class SegmentTree {
2
    private final long[] tree;
3
    private final int n;
4
 
5
    SegmentTree(int[] a) {
6
        n = a.length;
7
        // 4n never overflows even when n is not a power of two — the standard
8
        // allocation.
9
        tree = new long[4 * n];   // safe upper bound
10
        if (n > 0) build(a, 1, 0, n - 1);
11
    }
12
 
13
    private void build(int[] a, int node, int lo, int hi) {
14
        if (lo == hi) {
15
            tree[node] = a[lo];
16
            return;
17
        }
18
        int mid = (lo + hi) >>> 1;
19
        build(a, 2 * node, lo, mid);
20
        build(a, 2 * node + 1, mid + 1, hi);
21
        // Internal node = sum of its two children; used in both build and update.
22
        tree[node] = tree[2 * node] + tree[2 * node + 1];
23
    }
24
 
25
    void update(int i, int val) {
26
        update(1, 0, n - 1, i, val);
27
    }
28
 
29
    private void update(int node, int lo, int hi, int i, int val) {
30
        if (lo == hi) {
31
            tree[node] = val;
32
            return;
33
        }
34
        int mid = (lo + hi) >>> 1;
35
        if (i <= mid) {
36
            // Descend only into the child whose interval contains i — one path, O(log
37
            // n).
38
            update(2 * node, lo, mid, i, val);
39
        } else {
40
            update(2 * node + 1, mid + 1, hi, i, val);
41
        }
42
        tree[node] = tree[2 * node] + tree[2 * node + 1];
43
    }
44
 
45
    long rangeSum(int l, int r) {
46
        return query(1, 0, n - 1, l, r);
47
    }
48
 
49
    private long query(int node, int lo, int hi, int l, int r) {
50
        // No overlap with the query — return the identity 0 and stop descending.
51
        if (r < lo || hi < l) {
52
            return 0;                 // fully outside: additive identity
53
        }
54
        if (l <= lo && hi <= r) {
55
            // Total overlap — use the precomputed sum without recursing further. This
56
            // is why queries are O(log n).
57
            return tree[node];        // fully inside: stored sum
58
        }
59
        int mid = (lo + hi) >>> 1;
60
        return query(2 * node, lo, mid, l, r)
61
             + query(2 * node + 1, mid + 1, hi, l, r);
62
    }
63
 
64
    public static void main(String[] args) {
65
        SegmentTree st = new SegmentTree(new int[]{1, 3, 5, 7, 9, 11});
66
        System.out.println(st.rangeSum(1, 3)); // 15
67
        st.update(1, 10);
68
        System.out.println(st.rangeSum(1, 3)); // 22
69
        System.out.println(st.rangeSum(0, 5)); // 43
70
    }
71
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.71 lines

D · Why it works and complexityO(n) build, O(log n) query, O(log n) update timeO(n) spaceOpen the invariant and proofExplore the proof

The engine is interval decomposition: precompute the sum of a logarithmic set of nested intervals, and then every range is a union of O(log n) of them while every element belongs to only O(log n) of them. That symmetry — few intervals cover a range, few intervals contain a point — is what makes both query and update logarithmic. Swap the + merge and the 0 identity for min/+∞ or max/−∞ and the identical code answers range-min or range-max.

ComplexityO(n) build, O(log n) query, O(log n) update time, O(n) space — Build visits each of the O(n) tree nodes once → O(n). A query or update descends from the root; at each level it follows at most a constant number of partially-overlapping nodes, and the tree height is O(log n) → O(log n) per operation. The flat tree array uses O(n) space (4n is the safe bound).

E · Edge cases and pitfalls7n = 1 — Tree is a single leaf at the root; both query and update touch one node. The 4n allocation still works.Explore edge cases

Edge cases handled

n = 1Tree is a single leaf at the root; both query and update touch one node. The 4n allocation still works.
rangeSum(0, n-1)Whole-array query stops at the root in O(1) because the root's interval is fully inside.
Negative valuesSums work unchanged; use 64-bit (long) so large totals do not overflow.

Pitfalls

Allocating only 2n for the tree array — overflows when n is not a power of two; use 4n.
Returning the wrong identity in the no-overlap case (anything but 0 for sum) — silently wrong answers.
Forgetting to re-sum ancestors after an update — stale sums above the changed leaf.
Using int for the sum in Java when totals can exceed 2³¹ — overflow; use long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass SegmentTree { private final long[] tree; private final int n; SegmentTree(int[] a) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

class SegmentTree {
    private final long[] tree;
    private final int n;

SegmentTree(int[] a) {
        n = a.length;
        tree = new long[4 * n];   // safe upper bound
        if (n > 0) build(a, 1, 0, n - 1);
    }

private void build(int[] a, int node, int lo, int hi) {
        if (lo == hi) {
            tree[node] = a[lo];
            return;
        }
        int mid = (lo + hi) >>> 1;
        build(a, 2 * node, lo, mid);
        build(a, 2 * node + 1, mid + 1, hi);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

void update(int i, int val) {
        update(1, 0, n - 1, i, val);
    }

private void update(int node, int lo, int hi, int i, int val) {
        if (lo == hi) {
            tree[node] = val;
            return;
        }
        int mid = (lo + hi) >>> 1;
        if (i <= mid) {
            update(2 * node, lo, mid, i, val);
        } else {
            update(2 * node + 1, mid + 1, hi, i, val);
        }
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

long rangeSum(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

private long query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) {
            return 0;                 // fully outside: additive identity
        }
        if (l <= lo && hi <= r) {
            return tree[node];        // fully inside: stored sum
        }
        int mid = (lo + hi) >>> 1;
        return query(2 * node, lo, mid, l, r)
             + query(2 * node + 1, mid + 1, hi, l, r);
    }

public static void main(String[] args) {
        SegmentTree st = new SegmentTree(new int[]{1, 3, 5, 7, 9, 11});
        System.out.println(st.rangeSum(1, 3)); // 15
        st.update(1, 10);
        System.out.println(st.rangeSum(1, 3)); // 22
        System.out.println(st.rangeSum(0, 5)); // 43
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Tree array too small

When n is not a power of two, the recursion reaches node indices above 2n. Allocating 2n overflows the array; 4n is the safe bound that always fits.

Explore the code comparison

Don't write this

tree = new long[2 * n];   // index out of bounds for many n

Write this instead

tree = new long[4 * n];   // safe for any n

Wrong identity for no-overlap

When a node's interval is fully outside the query, it must contribute the additive identity 0 so it changes nothing. Returning a stored sum or a sentinel corrupts the merged result.

Explore the code comparison

Don't write this

if r < lo or hi < l:
    return self.tree[node]   # wrong: pollutes the sum

Write this instead

if r < lo or hi < l:
    return 0                 # additive identity

Not re-summing ancestors on update

A point update changes a leaf but every ancestor's stored sum also depended on it. If you set the leaf and return, all the sums above it are stale.

Explore the code comparison

Don't write this

def _update(self, node, lo, hi, i, val):
    if lo == hi:
        self.tree[node] = val
        return
    # ... recurse but forget to recombine the parent

Write this instead

    # ... recurse into the correct child, then:
    self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive interval tree: each node holds the aggregate of its sub-range

Code pattern to memorize

build(node, lo, hi):
    if lo == hi: tree[node] = a[lo]; return
    mid = (lo + hi) // 2
    build(2*node, lo, mid); build(2*node+1, mid+1, hi)
    tree[node] = tree[2*node] + tree[2*node+1]

Rules to remember

1Allocate the tree array with size 4n — a safe upper bound that avoids index overflow for any n.
2Each node covers [lo, hi]; recurse into the half (or halves) that overlap the query range.
3A query node returns 0 (the additive identity) when its range is fully outside the query — never recurse further there.
4A point update changes one leaf, then re-sums each ancestor on the way back up — that is the O(log n).
5The merge for sum is +; swap it for min, max, or gcd and the same structure handles those queries.

Use this pattern when

Many interleaved range queries AND point/range updates on the same array
Aggregates that compose associatively: sum, min, max, gcd, xor
Online queries where you cannot precompute all answers up front
When prefix sums break because the array keeps changing

Choose another pattern when

Array is static (no updates) → a prefix-sum array gives O(1) queries with no tree
Only point updates + prefix-sum queries → a Fenwick (BIT) tree is shorter to write
Aggregate is not associative (e.g. 'most frequent element') → segment tree merge breaks down
n is tiny and queries are few → a plain loop is simpler and fast enough

Interview takeaway

A segment tree buys balance: instead of fast-query/slow-update or slow-query/fast-update, both become O(log n). The whole idea is that any range decomposes into O(log n) precomputed canonical intervals, so you merge a handful of stored partials instead of scanning.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSegment tree: store an associative aggregate over every canonical interval so any range is a union of O(log n) nodes and any element belongs to O(log n) nodes. Reach for it when point/range updates and range queries are interleaved. Swap the merge (+, min, max, gcd) and its identity to handle other aggregates.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Range Sum Query - Mutable
Coming soon
This exact problem on LeetCode — segment tree or Fenwick tree both fit.
Lazy Propagation (Range Update)
Coming soon
Add a lazy[] array to defer range updates so range add + range sum are both O(log n).
Range Minimum Query
Coming soon
Swap the merge to min and the identity to +∞ — same tree, different aggregate.
Fenwick Tree (Binary Indexed Tree)
Shorter code for point update + prefix sum, the common special case of this problem.

Same pattern

←

Heavy-Light Decomposition (Path Queries)

Continue · Next problem

Maximum Weight Independent Set on a Tree

mediumTreesSometimes asked

Segment Tree for Range Sum

Trees & BST · 29 of 41 · 11 min

Design a data structure over an integer array a[0..n-1] that supports two operations efficiently after building:

1
**rangeSum(l, r)** — return the sum of a[l] + a[l+1] + … + a[r].
2
**update(i, val)** — set a[i] = val.

The operations are interleaved and there can be up to 10⁵ of each. Build once, then answer every operation in **O(log n)**.

In plain English

Examples

Example 1

Input: a = [1, 3, 5, 7, 9, 11]; rangeSum(1, 3)
Output: 15
Note: a[1] + a[2] + a[3] = 3 + 5 + 7 = 15.

Example 2

Input: a = [1, 3, 5, 7, 9, 11]; update(1, 10); rangeSum(1, 3)
Output: 22
Note: After a[1] becomes 10, the sum is 10 + 5 + 7 = 22.

Example 3

Input: a = [1, 3, 5, 7, 9, 11]; rangeSum(0, 5)
Output: 36
Note: The full-array sum is stored at the root, so this query returns in O(1) once the root is reached.

Constraints

1 ≤ n ≤ 10⁵
Up to 10⁵ mixed update and rangeSum calls
0 ≤ l ≤ r ≤ n − 1 for every query
Values fit in 64-bit after summation (use long in Java)

Clarifying questions4First question: Are updates point updates or range updates?Explore questions

Q1.Are updates point updates or range updates?
Point updates here (set one index). Range updates need lazy propagation, which is a layer on top of this same tree — worth mentioning as the follow-up.
Q2.Is the array static or changing?
Changing. If it were static, a prefix-sum array gives O(1) queries and no tree is needed — say that to show you reach for the simplest tool first.
Q3.What aggregate — sum, min, max?
Sum here, but the structure is identical for any associative merge. Only the combine step and the identity element change.
Q4.Could the recursion get deep enough to overflow the stack?
Depth is O(log n) ≈ 17 for n = 10⁵, so recursion is safe. For pedagogically deep structures you would switch to the iterative bottom-up segment tree, which I can mention.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Plain Array (Loop the Range)	`O(1) update, O(n) query`	`O(n)`	Say this first: it is correct and trivial, and it makes the cost trade-off obvious before you reach for a tree.	Read
2	Segment Tree — Recursive Array Implementation (Optimal)Optimal	`O(n) build, O(log n) query, O(log n) update`	`O(n)`	The answer they want once updates and queries are interleaved. 'Each node owns an interval and stores its sum; both operations walk O(log n) nodes.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Segment tree over [1,3,5,7]

How to read it:Each node stores the sum of its interval; the root holds the total. A query merges the few nodes that cover its range.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Plain Array (Loop the Range)

TimeO(1) update, O(n) querySpaceO(n)

Say this first: it is correct and trivial, and it makes the cost trade-off obvious before you reach for a tree.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Store the array as-is. update(i, val) is a single assignment — O(1).

2Hint 2Explore hint

rangeSum(l, r) loops from l to r adding each element — O(n) per query.

3Hint 3Explore hint

With up to 10⁵ queries each scanning up to 10⁵ elements, that is up to 10¹⁰ operations. Too slow — this motivates the tree.

A · Core idea

The simplest correct structure is the array itself.

Update is trivial. Setting a[i] = val is one assignment, O(1). Nothing else to maintain.

Query is a loop. To answer rangeSum(l, r) you add a[l] through a[r] directly — up to n additions in the worst case.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 5, 7, 9, 11]; rangeSum(1, 3)

i=1

sum += 3

Statesum = 3

Final result15

C · Code with teaching comments

Reference implementation previewclass RangeArray { private final long[] a; RangeArray(int[] input) { a = new long[input.length];Explore the full code

solution.javaJava

Baseline — Plain Array (Loop the Range) — reference

2 teaching notes

1
class RangeArray {
2
    private final long[] a;
3
 
4
    RangeArray(int[] input) {
5
        a = new long[input.length];
6
        for (int i = 0; i < input.length; i++) {
7
            a[i] = input[i];
8
        }
9
    }
10
 
11
    void update(int i, int val) {
12
        // Point update is a single write — the cheap operation here.
13
        a[i] = val;            // O(1)
14
    }
15
 
16
    long rangeSum(int l, int r) {
17
        long sum = 0;
18
        // Scanning the range is the expensive operation that the tree will fix.
19
        for (int i = l; i <= r; i++) {  // O(n)
20
            sum += a[i];
21
        }
22
        return sum;
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(1) update, O(n) query timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Using a prefix-sum array instead and forgetting that updates then cost O(n).Explore edge cases

Pitfalls

Using a prefix-sum array instead and forgetting that updates then cost O(n).
Assuming O(n) per query is fine — it is not when both n and the query count are ~10⁵.
Off-by-one on the inclusive r (loop to r, not r-1).

03.2

Approach 2 of 2 · Optimal

Segment Tree — Recursive Array Implementation (Optimal)

TimeO(n) build, O(log n) query, O(log n) updateSpaceO(n)

The answer they want once updates and queries are interleaved. 'Each node owns an interval and stores its sum; both operations walk O(log n) nodes.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build a binary tree where each node owns a contiguous sub-interval and stores the sum of that interval. The root owns [0, n-1].

2Hint 2Explore hint

For a query, classify each node three ways: its interval is fully outside the query (return 0), fully inside (return its stored sum), or partially overlapping (recurse into both children and add).

3Hint 3Explore hint

For an update, walk down to the single leaf for index i, set it, then re-sum each ancestor on the way back up. Store the tree in a flat array of size 4n; children of node v are 2v and 2v+1.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 5, 7]; build, then rangeSum(1, 3), then update(1, 10), rangeSum(1, 3)

Array state

after build

tree[1]=16 (root), tree[2]=4, tree[3]=12, tree[4..7]=1,3,5,7

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final result15 then 22

C · Code with teaching comments

solution.javaJava

Segment Tree — Recursive Array Implementation (Optimal) — optimal

5 teaching notes

1
class SegmentTree {
2
    private final long[] tree;
3
    private final int n;
4
 
5
    SegmentTree(int[] a) {
6
        n = a.length;
7
        // 4n never overflows even when n is not a power of two — the standard
8
        // allocation.
9
        tree = new long[4 * n];   // safe upper bound
10
        if (n > 0) build(a, 1, 0, n - 1);
11
    }
12
 
13
    private void build(int[] a, int node, int lo, int hi) {
14
        if (lo == hi) {
15
            tree[node] = a[lo];
16
            return;
17
        }
18
        int mid = (lo + hi) >>> 1;
19
        build(a, 2 * node, lo, mid);
20
        build(a, 2 * node + 1, mid + 1, hi);
21
        // Internal node = sum of its two children; used in both build and update.
22
        tree[node] = tree[2 * node] + tree[2 * node + 1];
23
    }
24
 
25
    void update(int i, int val) {
26
        update(1, 0, n - 1, i, val);
27
    }
28
 
29
    private void update(int node, int lo, int hi, int i, int val) {
30
        if (lo == hi) {
31
            tree[node] = val;
32
            return;
33
        }
34
        int mid = (lo + hi) >>> 1;
35
        if (i <= mid) {
36
            // Descend only into the child whose interval contains i — one path, O(log
37
            // n).
38
            update(2 * node, lo, mid, i, val);
39
        } else {
40
            update(2 * node + 1, mid + 1, hi, i, val);
41
        }
42
        tree[node] = tree[2 * node] + tree[2 * node + 1];
43
    }
44
 
45
    long rangeSum(int l, int r) {
46
        return query(1, 0, n - 1, l, r);
47
    }
48
 
49
    private long query(int node, int lo, int hi, int l, int r) {
50
        // No overlap with the query — return the identity 0 and stop descending.
51
        if (r < lo || hi < l) {
52
            return 0;                 // fully outside: additive identity
53
        }
54
        if (l <= lo && hi <= r) {
55
            // Total overlap — use the precomputed sum without recursing further. This
56
            // is why queries are O(log n).
57
            return tree[node];        // fully inside: stored sum
58
        }
59
        int mid = (lo + hi) >>> 1;
60
        return query(2 * node, lo, mid, l, r)
61
             + query(2 * node + 1, mid + 1, hi, l, r);
62
    }
63
 
64
    public static void main(String[] args) {
65
        SegmentTree st = new SegmentTree(new int[]{1, 3, 5, 7, 9, 11});
66
        System.out.println(st.rangeSum(1, 3)); // 15
67
        st.update(1, 10);
68
        System.out.println(st.rangeSum(1, 3)); // 22
69
        System.out.println(st.rangeSum(0, 5)); // 43
70
    }
71
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.71 lines

D · Why it works and complexityO(n) build, O(log n) query, O(log n) update timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7n = 1 — Tree is a single leaf at the root; both query and update touch one node. The 4n allocation still works.Explore edge cases

Edge cases handled

n = 1Tree is a single leaf at the root; both query and update touch one node. The 4n allocation still works.
rangeSum(0, n-1)Whole-array query stops at the root in O(1) because the root's interval is fully inside.
Negative valuesSums work unchanged; use 64-bit (long) so large totals do not overflow.

Pitfalls

Allocating only 2n for the tree array — overflows when n is not a power of two; use 4n.
Returning the wrong identity in the no-overlap case (anything but 0 for sum) — silently wrong answers.
Forgetting to re-sum ancestors after an update — stale sums above the changed leaf.
Using int for the sum in Java when totals can exceed 2³¹ — overflow; use long.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass SegmentTree { private final long[] tree; private final int n; SegmentTree(int[] a) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

class SegmentTree {
    private final long[] tree;
    private final int n;

SegmentTree(int[] a) {
        n = a.length;
        tree = new long[4 * n];   // safe upper bound
        if (n > 0) build(a, 1, 0, n - 1);
    }

void update(int i, int val) {
        update(1, 0, n - 1, i, val);
    }

long rangeSum(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Tree array too small

When n is not a power of two, the recursion reaches node indices above 2n. Allocating 2n overflows the array; 4n is the safe bound that always fits.

Explore the code comparison

Don't write this

tree = new long[2 * n];   // index out of bounds for many n

Write this instead

tree = new long[4 * n];   // safe for any n

Wrong identity for no-overlap

When a node's interval is fully outside the query, it must contribute the additive identity 0 so it changes nothing. Returning a stored sum or a sentinel corrupts the merged result.

Explore the code comparison

Don't write this

if r < lo or hi < l:
    return self.tree[node]   # wrong: pollutes the sum

Write this instead

if r < lo or hi < l:
    return 0                 # additive identity

Not re-summing ancestors on update

A point update changes a leaf but every ancestor's stored sum also depended on it. If you set the leaf and return, all the sums above it are stale.

Explore the code comparison

Don't write this

def _update(self, node, lo, hi, i, val):
    if lo == hi:
        self.tree[node] = val
        return
    # ... recurse but forget to recombine the parent

Write this instead

    # ... recurse into the correct child, then:
    self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Recursive interval tree: each node holds the aggregate of its sub-range

Code pattern to memorize

build(node, lo, hi):
    if lo == hi: tree[node] = a[lo]; return
    mid = (lo + hi) // 2
    build(2*node, lo, mid); build(2*node+1, mid+1, hi)
    tree[node] = tree[2*node] + tree[2*node+1]

Rules to remember

1Allocate the tree array with size 4n — a safe upper bound that avoids index overflow for any n.
2Each node covers [lo, hi]; recurse into the half (or halves) that overlap the query range.
3A query node returns 0 (the additive identity) when its range is fully outside the query — never recurse further there.
4A point update changes one leaf, then re-sums each ancestor on the way back up — that is the O(log n).
5The merge for sum is +; swap it for min, max, or gcd and the same structure handles those queries.

Use this pattern when

Many interleaved range queries AND point/range updates on the same array
Aggregates that compose associatively: sum, min, max, gcd, xor
Online queries where you cannot precompute all answers up front
When prefix sums break because the array keeps changing

Choose another pattern when

Array is static (no updates) → a prefix-sum array gives O(1) queries with no tree
Only point updates + prefix-sum queries → a Fenwick (BIT) tree is shorter to write
Aggregate is not associative (e.g. 'most frequent element') → segment tree merge breaks down
n is tiny and queries are few → a plain loop is simpler and fast enough

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Range Sum Query - Mutable
Coming soon
This exact problem on LeetCode — segment tree or Fenwick tree both fit.
Lazy Propagation (Range Update)
Coming soon
Add a lazy[] array to defer range updates so range add + range sum are both O(log n).
Range Minimum Query
Coming soon
Swap the merge to min and the identity to +∞ — same tree, different aggregate.
Fenwick Tree (Binary Indexed Tree)
Shorter code for point update + prefix sum, the common special case of this problem.

Same pattern

←

Heavy-Light Decomposition (Path Queries)

Continue · Next problem

Maximum Weight Independent Set on a Tree