Vultr DocsLatest Content

Range Sum Query - Mutable

Updated on 20 June, 2025
Range Sum Query - Mutable header image

Problem Statement

The task is to design a class NumArray which initially takes a list of integers nums and allows two main types of operations. The first type of operation involves updating the value of an element in the list at a specific index. The second type of operation is calculating the sum of a subarray defined between two indices left and right where both bounds are inclusive and within the range of the list. The class should efficiently handle multiple queries of both types without unnecessary re-computation, particularly under constraints where the operations and array size can scale significantly.

Examples

Example 1

Input:

["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Output:

[null, 9, null, 8]

Explanation:

NumArray numArray = new NumArray([1, 3, 5]);  
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9  
numArray.update(1, 2);   // nums becomes [1, 2, 5]  
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 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 will be made to update and sumRange.

Approach and Intuition

To efficiently handle the two operations described—updating an element and querying the sum of a subarray—several data structures and techniques can be considered:

1. Naive Approach

  • Update: O(1) — simple assignment at index.
  • Sum Query: O(k) — iterate from left to right, worst-case O(n).
  • Not scalable for large numbers of operations.

2. Segment Tree

  • Construction Time: O(n)

  • Update Time: O(log n)

  • Query Time: O(log n)

  • Details:

    • Store aggregate segment sums in a binary tree structure.
    • Modify only affected segments during update.
    • Efficiently combine relevant segments during sum queries.

3. Binary Indexed Tree (Fenwick Tree)

  • Update Time: O(log n)
  • Prefix Sum Time: O(log n)
  • Range Sum: Calculate as prefixSum(right) - prefixSum(left - 1)
  • Less memory overhead than segment tree, but trickier for range queries beyond prefix sum.

Solutions

  • Java
java 
public int calculateSum(int left, int right) {
    left += n;
    right += n;
    int total = 0;
    while (left <= right) {
        if ((left % 2) == 1) {
            total += tree[left];
            left++;
        }
        if ((right % 2) == 0) {
            total += tree[right];
            right--;
        }
        left /= 2;
        right /= 2;
    }
    return total;
}

The solution to "Range Sum Query - Mutable" involves using a segment tree to efficiently find the sum of elements within a given range. The provided Java code describes a method named calculateSum which calculates the sum between two indices, left and right.

  • The method adjusts the indices left and right by adding n, presumably the number of elements in the array, to shift them to the right position in a segment tree data structure.
  • A total variable is initialized to zero to store the sum of the elements in the specified range.
  • The method employs a while loop that runs as long as left is less than or equal to right.
    • When left is odd (left % 2 == 1), it indicates that left is at the rightmost position of its segment. The method adds the corresponding tree[left] value to total and increments left.
    • Conversely, when right is even (right % 2 == 0), indicating right is at the leftmost position of its segment, tree[right] is added to total and right is decremented.
    • After processing the values at left and right, both indices are divided by 2, essentially moving up one level in the segment tree.
  • The loop continues this process, aggregating values from the segment tree until the entire range is covered.
  • Finally, the method returns total, which is the sum of all elements from index left to right.

This technique allows for efficient range sum queries as well as updates, as segment trees provide a way to handle such operations in logarithmic time relative to the number of elements in the array. This approach is significantly more efficient than a simple iterative approach, especially useful for data sets where frequent queries and updates are expected.

Comments