Range Sum Query - Mutable

Medium Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Reported atGoldman Sachs

Range Sum Query - Mutable is a medium design data structures problem solved with the pre-processing + tradeoffs pattern. The best approach, optimal (fenwick tree), runs in O(log n) per call, O(n log n) to build time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (plain array) up.

Problem

Build a class NumArray over an integer array that supports two kinds of operations, mixed in any order.

NumArray(int[] nums) stores the starting array. update(int index, int val) sets nums[index] to val. sumRange(int left, int right) returns the sum of the elements from index left to index right, both included, using the current values.

Examples

Example 1

Input
NumArray([2, 5, -3, 4]), sumRange(0, 3), update(2, 6), sumRange(1, 2), sumRange(0, 3)
Output
8, 11, 17
Why
Initially 2 + 5 - 3 + 4 = 8. After index 2 becomes 6, the range [1, 2] is 5 + 6 = 11 and the whole array sums to 17.

Example 2

Input
NumArray([10]), sumRange(0, 0), update(0, -4), sumRange(0, 0)
Output
10, -4
Why
A one-element array: the range sum is just that element, before and after it changes.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (plain array)O(1) update, O(n) sumRangeO(n)
Optimal (Fenwick tree)O(log n) per call, O(n log n) to buildO(n)

1Brute force (plain array)

TimeO(1) update, O(n) sumRangeA query may scan the whole array; an update touches one slot.
SpaceO(n)One copy of the array.

Keep a copy of the array. Updates overwrite one slot; each range query loops over the range and adds it up.

  1. Constructor: copy nums.
  2. update(index, val): a[index] = val.
  3. sumRange(left, right): add a[left..right] and return it.
class NumArray {
    private final int[] a;

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

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

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

2Optimal (Fenwick tree)

TimeO(log n) per call, O(n log n) to buildEach walk changes one bit of the index per step, so at most log n steps.
SpaceO(n)The tree and the value array, each n + 1 entries.

A Fenwick tree stores in tree[i] (1-indexed) the sum of the block of length i & -i that ends at i. A prefix sum walks down by removing the lowest set bit; an update walks up by adding it. Keep the current values in a side array so update(index, val) can add val - old as a difference. sumRange(l, r) = prefix(r + 1) - prefix(l).

  1. Constructor: tree of size n + 1; for each i add nums[i] at position i + 1.
  2. add(i, delta): while i <= n: tree[i] += delta; i += i & -i.
  3. prefix(i): sum = 0; while i > 0: sum += tree[i]; i -= i & -i.
  4. update: delta = val - a[index]; a[index] = val; add(index + 1, delta).
  5. sumRange: prefix(right + 1) - prefix(left).
class NumArray {
    private final int n;
    private final int[] tree;
    private final int[] a;

    public NumArray(int[] nums) {
        n = nums.length;
        tree = new int[n + 1];
        a = nums.clone();
        for (int i = 0; i < n; i++) add(i + 1, nums[i]);
    }

    private void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }

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

    public void update(int index, int val) {
        add(index + 1, val - a[index]);
        a[index] = val;
    }

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

Edge cases to test

  • A range of a single index (left == right)
  • Updating an index to the value it already has
  • Updating the first or last index, then querying the full array
  • Many updates in a row with no queries in between

Hints

Hint 1

A plain array makes updates O(1) and sums O(n); a prefix-sum array does the opposite. Can both be O(log n)?

Hint 2

Store partial sums of blocks whose sizes are powers of two. A prefix sum is then a sum of O(log n) blocks, and an index belongs to O(log n) blocks.

Hint 3

A Fenwick (binary indexed) tree does exactly that: i & -i is the length of the block that ends at position i. Turn update into 'add the difference'.

FAQ

What is the best time complexity for Range Sum Query - Mutable?

Optimal (Fenwick tree) runs in O(log n) per call, O(n log n) to build time and O(n) extra space. Each walk changes one bit of the index per step, so at most log n steps.

Which pattern does Range Sum Query - Mutable use?

It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.

Is there a brute force solution for Range Sum Query - Mutable?

Yes. Brute force (plain array) takes O(1) update, O(n) sumRange time and O(n) space. Keep a copy of the array.

Which edge cases should I test for Range Sum Query - Mutable?

A range of a single index (left == right); Updating an index to the value it already has; Updating the first or last index, then querying the full array; Many updates in a row with no queries in between.