SpaceComplexity

Segment Tree vs Prefix Sum: When O(1) Loses to O(log n)

June 9, 202610 min read
dsaalgorithmsinterview-prepdata-structures
Segment Tree vs Prefix Sum: When O(1) Loses to O(log n)
TL;DR
  • Prefix sum answers range sum queries in O(1) but rebuilds in O(n) on any update — right for static arrays only
  • Segment tree handles both point updates and range queries in O(log n) for any associative operation: sum, min, max, GCD, XOR
  • Use a sparse table for static range min/max queries: O(n log n) build, O(1) query beats both
  • Fenwick tree is a simpler, faster-in-practice alternative to segment tree for sum-only update workloads
  • The most common interview mistake: implementing a segment tree when a 5-line prefix sum would have solved the problem
  • Practice LeetCode 303 then 307 back-to-back — identical setup, updates are the only difference

O(1) sounds better than O(log n). Faster in every textbook, every cheat sheet, every runtime comparison you've ever seen.

So why would you ever pick the slower one?

Because query time isn't the only cost. If your array changes between queries, the O(1) structure needs to rebuild every time an element shifts. That rebuild is O(n). Suddenly your "fast" structure is the slow one. The segment tree vs prefix sum decision is really asking: how often does your data change?

If your array never changes, use a prefix sum. If elements get updated between queries, use a segment tree.

That resolves about 80% of "which do I use?" situations. The rest of this post is the 20% that trips people up in interviews.

The Five-Line Structure That Beats Everything (Sometimes)

A prefix sum is an auxiliary array where prefix[i] stores the cumulative sum from index 0 through index i.

arr:    [ 3,  1,  4,  1,  5,  9,  2,  6]
idx:      0   1   2   3   4   5   6   7

prefix: [ 3,  4,  8,  9, 14, 23, 25, 31]
         [0] [1] [2] [3] [4] [5] [6] [7]

Any range sum query [l, r] answers in O(1): compute prefix[r] - prefix[l-1].

def build(arr):
    prefix = [0] * (len(arr) + 1)
    for i, val in enumerate(arr):
        prefix[i + 1] = prefix[i] + val
    return prefix

def query(prefix, l, r):  # inclusive [l, r], 0-indexed
    return prefix[r + 1] - prefix[l]

Build takes O(n) time and O(n) space. Each query is O(1). That combination is hard to beat for read-heavy workloads.

The catch: if you update arr[i], every prefix[j] where j > i becomes stale. Rebuilding costs O(n). For a workload that mixes one update with one query, you've just paid O(n) for what should feel cheap. The prefix sum's superpower is also its kryptonite.

The Tree That Won't Stop Growing

A segment tree stores aggregate values (sum, min, max, GCD, XOR, etc.) for every contiguous segment of the array. The root covers the full array. Children split it in half. Leaf nodes cover individual elements.

arr: [3, 1, 4, 1, 5, 9, 2, 6]

                    [31]              <- sum of all 8
           [9]              [22]      <- left half / right half
       [4]     [5]      [14]    [8]   <- quarters
     [3][1]  [4][1]   [5][9]  [2][6] <- leaves

This tree lives in a flat array sized 4n. A range query over [l, r] walks the tree combining nodes that fall fully inside the range and splitting those that partially overlap. Both query and point update run in O(log n), because the tree height is log n.

class SegmentTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self._build(nums, 0, 0, self.n - 1)

    def _build(self, nums, node, start, end):
        if start == end:
            self.tree[node] = nums[start]
            return
        mid = (start + end) // 2
        self._build(nums, 2 * node + 1, start, mid)
        self._build(nums, 2 * node + 2, mid + 1, end)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid:
            self.update(2 * node + 1, start, mid, idx, val)
        else:
            self.update(2 * node + 2, mid + 1, end, idx, val)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    def query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return (self.query(2 * node + 1, start, mid, l, r) +
                self.query(2 * node + 2, mid + 1, end, l, r))

The One Question That Settles It

OperationPrefix SumSegment Tree
BuildO(n)O(n)
Range queryO(1)O(log n)
Point updateO(n)O(log n)
Range updateO(n)O(log n) with lazy propagation
SpaceO(n)O(n)

Both structures use O(n) space and O(n) to build. The fork is entirely in updates: prefix sum wins on query speed when the array is static; segment tree wins when the array changes.

Ask yourself one thing before writing a single line of code: does this problem have updates? If yes, segment tree. If no, you probably don't need one.

Don't Touch the Segment Tree (When This Applies)

Prefix sum wins on simplicity. There's almost no code to write and no way to corrupt a complex structure under time pressure.

Use prefix sum when:

  1. The array is static. LeetCode 303 (Range Sum Query - Immutable) is the direct example.
  2. You're counting subarrays with a target property. The prefix[j] - prefix[i] = k trick (LeetCode 560) runs O(n) with a hash map. No segment tree formulation exists for this.
  3. You need 2D range sums. A 2D prefix sum builds in O(mn) and answers any rectangle query in O(1). A 2D segment tree exists but the interview code is brutal to write.
  4. You're operating under time pressure and the problem description mentions no updates.

For static sum queries or subarray counting problems, prefix sum is almost always the right tool. Reaching for a segment tree there wastes 20 minutes implementing something a five-line prefix sum would have handled.

Worked Example: LeetCode 560 (Subarray Sum Equals K)

Given an array and target k, count subarrays whose elements sum to k. The prefix[j] - prefix[i] = k reframing solves it in O(n):

def subarray_sum(nums, k):
    count = 0
    running = 0
    seen = {0: 1}
    for num in nums:
        running += num
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

A segment tree makes this problem harder, not easier. Five lines. Done. Go home.

When Your Array Betrays You

Use segment tree when the array mutates. If an element changes and you need to answer a range query afterward, prefix sum forces an O(n) rebuild. A segment tree handles both in O(log n).

Specific signals:

  1. The problem mixes point updates and range queries. LeetCode 307 (Range Sum Query - Mutable) is the direct comparison to 303.
  2. You need range minimum or maximum with updates. A prefix min/max array only answers queries starting from index 0. For arbitrary [l, r] with changes, it breaks entirely.
  3. The merge operation isn't sum. Segment trees support any associative operation: GCD, XOR, maximum prefix sum, range product. Prefix arrays are sum-only.
  4. The problem involves range updates. Lazy propagation lets you apply "add 5 to every element in [l, r]" in O(log n) instead of touching every element.

Worked Example: LeetCode 307 (Range Sum Query - Mutable)

Build a structure supporting both update(i, val) and sum_range(l, r).

With prefix sum, each update costs O(n). With the iterative segment tree below, both cost O(log n) and the structure uses only 2n space:

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        for i, val in enumerate(nums):
            self.tree[self.n + i] = val
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, val):
        pos = index + self.n
        self.tree[pos] = val
        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

    def sum_range(self, left, right):
        left += self.n
        right += self.n + 1
        total = 0
        while left < right:
            if left & 1:
                total += self.tree[left]
                left += 1
            if right & 1:
                right -= 1
                total += self.tree[right]
            left >>= 1
            right >>= 1
        return total

Range Min With Updates Will Ruin Your Day

Range minimum is where the prefix sum approach collapses. A prefix_min[i] = min(arr[0..i]) array only answers queries anchored at index 0. For arbitrary [l, r], it does nothing.

The segment tree handles range min/max natively. The only change from the sum version is the merge operation:

# Sum version:
self.tree[node] = self.tree[left] + self.tree[right]

# Min version:
self.tree[node] = min(self.tree[left], self.tree[right])

# Max version:
self.tree[node] = max(self.tree[left], self.tree[right])

If you see a range minimum or maximum problem with updates, that is a segment tree signal. Full stop.

One line change. Still O(log n). The structure doesn't care what you're aggregating, as long as the operation is associative.

Wait, There's a Third Option

For static range minimum or maximum queries, there's a better option than either structure. A sparse table builds in O(n log n) and answers any range min/max query in O(1) by exploiting overlapping power-of-2 intervals.

The decision tree for static arrays:

Static array?
├── Sum queries     → prefix sum    (O(n) build, O(1) query)
├── Min/max queries → sparse table  (O(n log n) build, O(1) query)
└── Both / other    → segment tree  (O(n) build, O(log n) query)

Dynamic array (updates allowed)?
└── Any query type  → segment tree  (O(n) build, O(log n) everything)

A Fenwick tree is worth mentioning here too. It handles sum queries with updates in O(log n), like a segment tree, but with smaller constants and simpler code. The tradeoff: Fenwick trees only support sum (and similar prefix-decomposable operations). They can't do range min or max. When sum with updates is all you need, a Fenwick tree is usually the cleaner choice over a full segment tree.

The Flowchart You Actually Need

  1. Does the problem have updates between queries?

    • No: prefix sum (sum) or sparse table (min/max).
    • Yes: segment tree (or Fenwick tree for sum-only).

  2. Is the query operation sum, or something else?

    • Sum with no updates: prefix sum.
    • Min/max with no updates: sparse table.
    • Anything with updates: segment tree.

  3. Are you counting subarrays by sum?

    • Almost certainly prefix sum plus hash map. Segment tree will not help.

The most common mistake is reaching for a segment tree because it feels more powerful, then wasting time implementing it when a prefix sum would have solved the problem in 10 lines.

Practice both back to back: LeetCode 303 then LeetCode 307. The setup is nearly identical. Updates are the only difference. Seeing both in one sitting makes the tradeoff visceral in a way reading about it doesn't.

If you want to practice identifying the pattern under actual interview conditions, SpaceComplexity runs voice-based mock interviews with rubric feedback on exactly this kind of data structure choice. The segment tree vs prefix sum decision comes up often enough that it's worth having an automatic response before you walk in.

Further Reading