Free lesson · DSA Mastery - Interview Prep, End to End

Range Sum Query - Mutable

Hard7 min readdsaadvanced-topics

Range Sum Query - Mutable

Range Sum Query - Mutable opens the Advanced Data Structures sub-group with a foundational problem: support an array with two operations - update a single element and query the sum of a range - both in O(log n). A prefix-sum array gives O(1) query but O(n) update; a plain array gives O(1) update but O(n) query. Neither suffices alone. The canonical solution is the Fenwick tree (Binary Indexed Tree, BIT): both operations in O(log n) with O(n) space. Segment trees achieve the same complexities with more flexibility but more code. We present the Fenwick tree (canonical) and segment tree (alternative).

The insight: the Fenwick tree decomposes any prefix sum [0, i] into O(log n) overlapping pieces - each tracked at a specific tree node. Updates touch O(log n) pieces; prefix queries combine O(log n) pieces. Range query [l, r] becomes prefix(r) - prefix(l - 1). The magic is in the low-bit operation i & (-i), which encodes the tree's hierarchical layout into clean bitwise arithmetic.

The Problem

Given an integer array nums, handle multiple queries of the following types:

1. Update the value of an element in nums.
2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums): Initializes the object with the integer array nums.
• void update(int index, int val): Updates the value of nums[index] to be val.
• int sumRange(int left, int right): Returns the sum of the elements of nums between indices left and right inclusive.

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output: [null, 9, null, 8]

Explanation: nums = [1, 3, 5]; sumRange(0, 2) = 9; update(1, 2) → nums = [1, 2, 5]; sumRange(0, 2) = 8.

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.

Approaches Overview

Approach: Fenwick Tree - Canonical

The Idea

The Fenwick tree is an array bit[1..n] where bit[i] stores the sum of nums[(i - lowbit(i)) .. i - 1] (a specific range ending at index i - 1). The function lowbit(i) = i & (-i) extracts the lowest set bit of i.

• Point update at index i: walk upward via i += lowbit(i), adding the delta at each visited BIT node. O(log n) nodes total.
• Prefix query sum(0..i): walk downward via i -= lowbit(i), accumulating bit[i] at each step until i = 0. O(log n) pieces total.
• Range query sum(l..r) = prefix(r + 1) - prefix(l) using 1-indexed BIT conventions.

Logic Flowchart

graph TD
    A["bit array of size n + 1, all zeros"] --> B["build: for each i, call update(i, nums[i])"]
    B --> C["update(index, val): delta = val - prev[index]"]
    C --> D["i = index + 1; while i <= n: bit[i] += delta; i += i & -i"]
    D --> E["prev[index] = val"]
    F["sumRange(left, right): return prefix(right + 1) - prefix(left)"]
    G["prefix(i): sum = 0; while i > 0: sum += bit[i]; i -= i & -i; return sum"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the Fenwick tree operations: update walks upward via low-bit additions; prefix query walks downward via low-bit subtractions.

Code

class NumArray {
    private int n;
    private int[] bit;
    private int[] arr;

    public NumArray(int[] nums) {
        n = nums.length;
        bit = new int[n + 1];
        arr = new int[n];
        for (int i = 0; i < n; i++) update(i, nums[i]);
    }

    public void update(int index, int val) {
        int delta = val - arr[index];
        arr[index] = val;
        for (int i = index + 1; i <= n; i += i & -i) bit[i] += delta;
    }

    public int sumRange(int left, int right) {
        return prefix(right + 1) - prefix(left);
    }

    private int prefix(int i) {
        int sum = 0;
        while (i > 0) {
            sum += bit[i];
            i -= i & -i;
        }
        return sum;
    }
}

// Usage:
// NumArray na = new NumArray(new int[]{1,3,5});
// na.sumRange(0, 2)  -> 9
// na.update(1, 2);
// na.sumRange(0, 2)  -> 8

This Java code implements Range Sum Query Mutable via a Fenwick tree with point update and prefix query.

Step-by-Step Walkthrough

Tracing operations on [1, 3, 5]:

graph LR
    F0["Build (1-indexed BIT of size 4): after update(0,1): bit=[_,1,1,0]; after update(1,3): bit=[_,1,4,0]; after update(2,5): bit=[_,1,4,5]"]
    F1["sumRange(0, 2) = prefix(3) - prefix(0) = (bit[3] + bit[2]) - 0 = 5 + 4 = 9"]
    F2["update(1, 2): delta = 2 - 3 = -1; walk i=2 → bit[2] += -1 → bit=[_,1,3,5]; next i=4 exceeds n=3, stop"]
    F3["sumRange(0, 2) = prefix(3) - prefix(0) = (bit[3] + bit[2]) - 0 = 5 + 3 = 8"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough traces a sample sequence of build, query, update, query operations on a three-element array.

Result: queries return 9 then 8.

Complexity

Build: O(n log n). Update: O(log n). Query: O(log n). Space: O(n).

Complexity Comparison

The Fenwick tree is the canonical solution for point-update + range-sum queries. The segment tree is preferred when the operation isn't invertible (e.g., min/max queries) or when range updates with lazy propagation are needed.

Variations & Follow-ups

Why does the low-bit trick work?

For any positive integer i, i & (-i) extracts the lowest set bit. For example, i = 12 = 1100₂; -12 = ...11110100₂ (two's complement); 12 & -12 = 0100₂ = 4.

This bit identifies the "responsibility range" of bit[i]: it covers the lowbit(i) original elements ending at index i - 1. The hierarchical structure: every prefix [0, i) decomposes into a chain of these ranges. Walking down via i -= lowbit(i) traverses the chain.

The general lesson: the Fenwick tree's correctness is entirely encoded in the low-bit arithmetic. Once you internalize the low-bit step, both update and query become symmetric while loops.

Why is Fenwick build O(n log n) and not O(n)?

The straightforward build calls update(i, nums[i]) for each i, costing O(log n) each, total O(n log n).

A linear O(n) build exists: initialize bit[i] = nums[i - 1] directly, then for each i from 1 to n, propagate bit[i] to its parent bit[i + lowbit(i)] if within bounds. Each cell touched O(1) total. The improvement is constant-factor in practice; rarely needed unless build cost is critical.

When is segment tree preferred?

• Non-invertible operations: min, max, gcd, bitwise-and. Fenwick tree relies on subtracting prefixes (sum(l..r) = prefix(r) - prefix(l-1)), which requires an inverse operation. Segment trees support any associative monoid.
• Range updates: with lazy propagation, segment trees handle "add x to every element in [l, r]" in O(log n). Fenwick trees can do this for point queries via a difference trick, but range queries require two BITs (more on this in 32.10 Falling Squares).
• Persistent variants: persistent segment trees enable historical queries; Fenwick doesn't naturally extend.

How does the segment tree compare?

A segment tree allocates ~4n nodes. Each node stores the aggregate (sum) of its range. Point update: descend to the leaf, update, climb back up combining. Range query: traverse only nodes fully inside [l, r], returning their aggregates and combining.

Both Fenwick and segment trees have the same asymptotic complexities. Fenwick is more compact (n + 1 cells) and faster by constant factors; segment trees are more flexible.

What about edge cases?

• n = 1: bit has 2 cells; update and query trivially work.
• All zeros initial: build is O(n) effective (no work in update calls when delta is 0).
• Negative values: BIT handles signed sums without modification.
• Repeated updates to the same index: each delta is val - prev[index], correctly tracking cumulative change.

Common Interview Pitfalls

• Off-by-one between 0-indexed and 1-indexed. Fenwick uses 1-indexed internally; convert index to index + 1 when passing in.
• Forgetting to track arr[index] for computing deltas. Without it, you can't translate "set to val" into "add delta."
• Using Fenwick for non-invertible operations. Min/max don't support prefix subtraction; use segment tree.
• Indexing bit[0]: it's a sentinel, never used. Operations start at index 1.

Why This Topic Matters

Range Sum Query - Mutable introduces the Fenwick tree and segment tree - the two foundational data structures for the entire Advanced Data Structures sub-group. The low-bit decomposition trick is one of the most elegant ideas in competitive programming, and segment trees recur throughout the rest of the sub-group (lazy propagation in 32.10, 2D variants in 32.8, augmented variants in 32.9).

The next topic, Range Sum Query 2D - Mutable, extends the problem to a 2D grid: support point updates and rectangle sum queries on an m × n matrix. The canonical solution is a 2D Fenwick tree - two nested low-bit loops achieve O(log m · log n) per operation. It's a direct generalization of 1D BIT and a key tool for 2D range problems.

Back to DSA Mastery - Interview Prep, End to End