Range Sum Query Mutable — Segment Tree and Fenwick Tree Explained

Problem Statement

LeetCode 307 — Range Sum Query - Mutable | Difficulty: Medium

Given a mutable integer array nums, implement a data structure that supports two operations efficiently:

update(index, val) — set nums[index] = val
sumRange(left, right) — return the sum of elements from index left to right (inclusive)

Constraints:

1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
At most 3 * 10^4 calls to update and sumRange

Example 1:

Input:  nums = [1, 3, 5]
        update(1, 2)      → nums becomes [1, 2, 5]
        sumRange(0, 2)    → 8

Example 2:

Input:  nums = [9, -8]
        update(0, 3)      → nums becomes [3, -8]
        sumRange(1, 1)    → -8
        sumRange(0, 1)    → -5

Example 3:

Input:  nums = [0, 0, 0, 0, 0]
        sumRange(0, 4)    → 0
        update(2, 5)      → nums becomes [0, 0, 5, 0, 0]
        sumRange(0, 4)    → 5

Why This Problem Matters

This is the canonical benchmark problem for range query data structures. Every engineering interview that touches databases, stream processing, or competitive programming will test some variant of this idea.

The naive approach — prefix sums — gives O(1) queries but O(n) updates. Mutable arrays break prefix sums entirely. The moment you need both fast queries and fast updates, you need a Fenwick Tree or Segment Tree. Mastering this problem teaches you the core trade-off that drives the design of real-world databases and search indexes.

The Core Insight

The key insight: precompute partial sums at multiple granularities so each update and query only touches O(log n) positions.

Binary Indexed Tree (Fenwick Tree)

A BIT stores partial sums indexed by the lowest set bit of each index. The trick is the expression i & (-i), which isolates the lowest set bit:

Update: walk forward by adding i & (-i) — propagate change upward
Query: walk backward by subtracting i & (-i) — accumulate prefix sum

BIT index (1-based):
  bit[1] = sum of nums[1..1]
  bit[2] = sum of nums[1..2]
  bit[3] = sum of nums[3..3]
  bit[4] = sum of nums[1..4]
  bit[6] = sum of nums[5..6]

Each index is responsible for a range whose length equals its lowest set bit. This gives O(log n) coverage of any prefix.

Segment Tree

Divides the array recursively into halves. Each node stores the aggregate (here, sum) of its range. Query and update both walk the tree in O(log n).

Visual Dry Run

Array: [1, 3, 5], BIT (1-indexed internally):

Build:

update(1, 1): bit[1]+=1, bit[2]+=1 → bit=[0,1,1,0]
update(2, 3): bit[2]+=3, bit[4]+=3 → bit=[0,1,4,0]  (bit[4] out of range, skip)
update(3, 5): bit[3]+=5             → bit=[0,1,4,5]

sumRange(0, 2) → query(3) - query(-1):

query(3): bit[3]=5, then i=3-1=2 → bit[2]=4+5=? 
  i=3: s+=bit[3]=5, i=3-(3&-3)=3-1=2
  i=2: s+=bit[2]=4 → s=9, i=2-(2&-2)=2-2=0 → stop
query(0) = 0
sumRange = 9 - 0 = 9  ✓  (1+3+5=9)

update(1, 2): delta = 2-3 = -1

i=2: bit[2]+=-1=3, i=2+(2&-2)=4 → out of range, stop
bit now: [0,1,3,5]
sumRange(0,2) = query(3)-query(-1) = (5+3)-(0) = 8  ✓

Common Mistakes

Off-by-one on BIT indices. BIT is 1-indexed internally. When update(index, val) is called with 0-indexed input, always do index + 1 before touching the BIT.
Forgetting to store the original array. The update method receives a new value, not a delta. You must compute delta = val - current_value, which requires knowing current_value. Either keep a separate nums array or compute it via sumRange(index, index).
Wrong BIT range boundary. In update, the loop condition is i <= n (not i < n). Missing this truncates updates at the last power-of-two.
Segment tree size. Allocating 2*n is only safe for perfect-power-of-two sizes. Always allocate 4*n to handle arbitrary n safely.
Not propagating after update in segment tree. After recursing into a child, you must recalculate the parent node: tree[node] = tree[2*node] + tree[2*node+1]. Forgetting this leaves stale values in ancestors.
Querying out-of-range indices. In the segment tree query, the base case qr < l or r < ql must be checked first with an early return of the identity element (0 for sum). If you mix up l, r, ql, qr, you get wrong answers silently.

Solutions

Python — BIT (Fenwick Tree)

class NumArray:
    def __init__(self, nums: list[int]):
        self.n = len(nums)          # store array length
        self.nums = nums[:]         # keep original values for delta computation
        self.bit = [0] * (self.n + 1)  # 1-indexed BIT array
        for i, v in enumerate(nums):   # build BIT by updating each position
            self._bit_update(i + 1, v) # convert to 1-indexed
 
    def _bit_update(self, i: int, delta: int) -> None:
        # walk forward adding lowest-set-bit to propagate change upward
        while i <= self.n:
            self.bit[i] += delta     # add delta to this responsible range
            i += i & (-i)            # jump to next responsible ancestor
 
    def _bit_query(self, i: int) -> int:
        # accumulate prefix sum [1..i]
        s = 0
        while i > 0:
            s += self.bit[i]         # add this node's partial sum
            i -= i & (-i)            # jump to left sibling range
        return s
 
    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]  # compute change from old to new value
        self.nums[index] = val          # record new value for future deltas
        self._bit_update(index + 1, delta)  # apply delta to BIT (1-indexed)
 
    def sumRange(self, left: int, right: int) -> int:
        # prefix sum trick: sum[left..right] = prefix[right+1] - prefix[left]
        return self._bit_query(right + 1) - self._bit_query(left)

Python — Segment Tree

class NumArray:
    def __init__(self, nums: list[int]):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)  # 4n nodes covers all cases
        self._build(nums, 1, 0, self.n - 1)  # root is node 1
 
    def _build(self, a: list[int], node: int, l: int, r: int) -> None:
        if l == r:                          # leaf node: store single element
            self.tree[node] = a[l]
            return
        mid = (l + r) // 2
        self._build(a, 2 * node, l, mid)       # build left child
        self._build(a, 2 * node + 1, mid + 1, r)  # build right child
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]  # merge
 
    def _update(self, node: int, l: int, r: int, i: int, v: int) -> None:
        if l == r:                          # found target leaf
            self.tree[node] = v
            return
        mid = (l + r) // 2
        if i <= mid:                        # target is in left subtree
            self._update(2 * node, l, mid, i, v)
        else:                               # target is in right subtree
            self._update(2 * node + 1, mid + 1, r, i, v)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]  # re-aggregate
 
    def _query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
        if qr < l or r < ql:               # query range doesn't overlap this node
            return 0                        # identity element for sum
        if ql <= l and r <= qr:            # this node is fully inside query range
            return self.tree[node]
        mid = (l + r) // 2
        left_sum = self._query(2*node, l, mid, ql, qr)        # query left
        right_sum = self._query(2*node+1, mid+1, r, ql, qr)   # query right
        return left_sum + right_sum
 
    def update(self, index: int, val: int) -> None:
        self._update(1, 0, self.n - 1, index, val)  # root=1, full range
 
    def sumRange(self, left: int, right: int) -> int:
        return self._query(1, 0, self.n - 1, left, right)

JavaScript — BIT (Fenwick Tree)

class NumArray {
    constructor(nums) {
        this.n = nums.length;
        this.nums = [...nums];                  // copy for delta computation
        this.bit = new Array(this.n + 1).fill(0); // 1-indexed BIT
        for (let i = 0; i < this.n; i++) {
            this._bitUpdate(i + 1, nums[i]);    // build BIT
        }
    }
 
    _bitUpdate(i, delta) {
        // propagate delta upward through BIT ancestors
        while (i <= this.n) {
            this.bit[i] += delta;               // update responsible range
            i += i & (-i);                      // move to next ancestor
        }
    }
 
    _bitQuery(i) {
        // accumulate prefix sum from index 1 to i
        let s = 0;
        while (i > 0) {
            s += this.bit[i];                   // add partial sum
            i -= i & (-i);                      // move to covered left boundary
        }
        return s;
    }
 
    update(index, val) {
        const delta = val - this.nums[index];   // compute delta
        this.nums[index] = val;                 // record new value
        this._bitUpdate(index + 1, delta);      // apply to BIT (1-indexed)
    }
 
    sumRange(left, right) {
        // range sum = prefix[right+1] - prefix[left]
        return this._bitQuery(right + 1) - this._bitQuery(left);
    }
}

Complexity Analysis

Approach	Build Time	Update Time	Query Time	Space
Naive array	O(n)	O(1)	O(n)	O(n)
Prefix sum (immutable)	O(n)	O(n)	O(1)	O(n)
BIT (Fenwick Tree)	O(n log n)	O(log n)	O(log n)	O(n)
Segment Tree	O(n)	O(log n)	O(log n)	O(n)

Segment Tree has a slightly better build time (O(n) vs O(n log n)) and handles a wider variety of queries, but BIT has a smaller constant factor and simpler code.

Follow-up Questions

What if you need range updates (add delta to all elements in [l, r]) and point queries? The BIT can be adapted using a difference array trick — update two endpoints instead of one.
What if you need range updates AND range queries? Use two BITs with the formula sum[l..r] = BIT_product at r - BIT_product at l-1. Or use a Segment Tree with lazy propagation.
What if the query is range minimum instead of range sum? BIT cannot handle range minimum (it's not invertible). You need a Segment Tree.
Can you handle dynamic array insertion/deletion? Use an Order-Statistics Tree or a Balanced BST (e.g., a policy-based tree in C++).
What if nums contains very large values? No change to the algorithm — Python handles arbitrary integers natively; in JS/C++ watch for overflow and use BigInt / long long.

This Pattern Solves

Any problem requiring O(log n) point updates and range aggregate queries
Leaderboard / ranking systems with frequent score updates
Time-series analytics with rolling window sums
Counting inversions, smaller elements, range frequency
2D variants: 2D BIT for rectangle sum queries

Key Takeaways

When an array is mutable and you need repeated range queries, prefix sums break — BIT or Segment Tree is the answer.
BIT solves point-update + prefix-sum in O(log n) using i & (-i) to navigate; update walks forward, query walks backward.
Segment Tree handles any associative operation (sum, min, max, GCD) with range queries in O(log n).
BIT has a smaller constant factor and simpler code; Segment Tree is more general and supports range updates via lazy propagation.
Always allocate 4*n nodes for a Segment Tree — 2*n only works for perfect power-of-two array sizes.
The delta approach in BIT update (compute delta = new - old) is critical — store the original array to enable this.
Segment Tree out-of-range nodes must return the identity element (0 for sum, INF for min) not an arbitrary value.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Binary Indexed Tree (Fenwick Tree)#

Segment Tree#

Visual Dry Run#

Common Mistakes#

Solutions#

Python — BIT (Fenwick Tree)#

Python — Segment Tree#

JavaScript — BIT (Fenwick Tree)#

Complexity Analysis#

Follow-up Questions#

This Pattern Solves#

Key Takeaways#

Related reading