Range Sum Query - Mutable

MediumRange Query · Fenwick Tree (BIT)🧩 Fenwick & Segment Tree LeetCode #307 ↗Updated Oct 30, 2026

Problem

Design a class NumArray built from an integer array nums that supports two operations, mixed in any order: update(index, val) overwrites nums[index] with val, and sumRange(left, right) returns the sum of nums[left..right] (both ends inclusive).

InputNumArray([1,3,5]); sumRange(0,2); update(1,2); sumRange(0,2)Output[null, 9, null, 8]

InputNumArray([-4]); sumRange(0,0); update(0,7); sumRange(0,0)Output[null, -4, null, 7]

1 ≤ n ≤ 3·10⁴ · -100 ≤ nums[i], val ≤ 100 · at most 3·10⁴ calls to update and sumRange

Try it yourself

Java

class NumArray {
    public NumArray(int[] nums) {
        
    }

    public void update(int index, int val) {
        
    }

    public int sumRange(int left, int right) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A plain prefix-sum array makes queries O(1) but updates O(n). A Fenwick tree stores partial sums over power-of-two blocks so that both a prefix query and a point update touch only O(log n) cells.

PatternFenwick & Segment Tree

Instinct Range sums, mins or counts asked again and again while values keep changing: prefix sums break, so reach for a Fenwick or segment tree.

Memory hack Prefix sums freeze, trees breathe: climb by the last set bit (i & -i) for Fenwick, split in halves for segment trees.

Open the Fenwick & Segment Tree guide →

Approaches

Brute ForcePlain Array, Sum on Demand

Time update O(1), sumRange O(n)Space O(n)

Keep a copy of the array. An update is a single assignment; a query loops from left to right adding values. Nothing is precomputed, so nothing goes stale.

Java

class NumArray {
    private final int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums.clone();
    }

    public void update(int index, int val) {
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) sum += nums[i];
        return sum;
    }
}

Fine when queries are rare; 3·10⁴ full-range queries cost ~10⁹ adds.

BetterSquare-Root Decomposition

Time update O(1), sumRange O(√n)Space O(n)

Cut the array into blocks of length about √n and keep each block's total. An update fixes one block total by the delta. A query adds the partial blocks at both ends element by element and the full blocks in between via their totals — at most about 3√n additions.

Java

class NumArray {
    private final int[] nums;
    private final int[] blocks; // blocks[b] = sum of block b
    private final int len;      // block length

    public NumArray(int[] nums) {
        this.nums = nums.clone();
        len = Math.max(1, (int) Math.sqrt(nums.length));
        blocks = new int[(nums.length + len - 1) / len];
        for (int i = 0; i < nums.length; i++) blocks[i / len] += nums[i];
    }

    public void update(int index, int val) {
        blocks[index / len] += val - nums[index];
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        int bl = left / len, br = right / len, sum = 0;
        if (bl == br) {
            for (int i = left; i <= right; i++) sum += nums[i];
            return sum;
        }
        for (int i = left; i < (bl + 1) * len; i++) sum += nums[i]; // left tail
        for (int b = bl + 1; b < br; b++) sum += blocks[b];          // whole blocks
        for (int i = br * len; i <= right; i++) sum += nums[i];     // right head
        return sum;
    }
}

Simple and balanced, but √n per query is still far from logarithmic.

OptimalFenwick Tree (Binary Indexed Tree)

Time build O(n), update / sumRange O(log n)Space O(n)

tree[i] (1-based) holds the sum of the last i & -i elements ending at position i. A prefix sum hops down by stripping the lowest set bit; an update hops up by adding it — each at most log n steps. A range sum is the difference of two prefix sums.

Java

class NumArray {
    private final int[] nums;
    private final int[] tree; // 1-based Fenwick tree

    public NumArray(int[] nums) {
        int n = nums.length;
        this.nums = nums.clone();
        tree = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] += nums[i - 1];
            int parent = i + (i & -i);
            if (parent <= n) tree[parent] += tree[i]; // linear-time build
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        for (int i = index + 1; i < tree.length; i += i & -i) tree[i] += delta;
    }

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

    private int prefix(int i) { // sum of nums[0..i-1]
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
}

Logarithmic for both operations with a tiny, array-only structure.

Pro tip

Store the current values in nums so updates can compute the delta — the tree only understands “add x”, not “set to x”.

At a glance

Level	Approach	Time	Space
Brute Force	Plain Array, Sum on Demand	`update O(1), sumRange O(n)`	`O(n)`
Better	Square-Root Decomposition	`update O(1), sumRange O(√n)`	`O(n)`
Optimal	Fenwick Tree (Binary Indexed Tree)	`build O(n), update / sumRange O(log n)`	`O(n)`

Common pitfalls

Adding val instead of val - old to the tree on update.
Mixing 0-based array indices with the 1-based Fenwick tree (off-by-one).
Rebuilding a prefix-sum array on every update — back to O(n) per call.

Interview tips

Start from immutable prefix sums (303) and explain exactly why updates break them.
Offer √n decomposition as a quick middle ground before the BIT.
Mention a segment tree as the more general alternative (min/max, range updates).

Pattern

Fenwick / segment tree → interleaved point updates and range aggregate queries on an array.

My notes saved in this browser