Interview AiBox logo
Interview AiBox
#307
Medium
auto_awesomeArray plus Design

LeetCode Problem Workspace

Range Sum Query - Mutable

Implement a mutable range sum query using efficient design patterns to handle multiple updates and range sum queries.

arraydesignbinary indexed treesegment tree
category

4

Topics

code_blocks

6

Code langs

hub

3

Related

play_arrowStart Solutionarrow_forward
speedComplexityopen_in_newLeetCode

Practice Focus

Medium · Array plus Design

bolt

Answer-first summary

Implement a mutable range sum query using efficient design patterns to handle multiple updates and range sum queries.

Interview AiBox logo

Ace coding interviews with Interview AiBox guidance for Array plus Design

Try AiBox Copilotarrow_forward

The problem requires handling multiple range sum queries and updates on an integer array. Efficient solutions are required for dynamic updates, using techniques like Segment Trees or Binary Indexed Trees to optimize time complexity for both sum queries and updates.

Problem Statement

You are tasked with implementing the NumArray class, which allows you to perform multiple operations on an integer array. The operations include updating an element at a specific index and querying the sum of elements within a specific range of indices.

The class should support two main operations: update(index, val) which sets the value at the specified index to val, and sumRange(left, right) which returns the sum of the elements in the array from index left to index right (inclusive). The solution must handle these operations efficiently given the constraints.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 = [1, 2, 5] numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Constraints

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • At most 3 * 104 calls will be made to update and sumRange.

Solution Approach

Brute Force Approach

In a brute force approach, we could iterate through the range on each query and sum the elements. While simple, this would have O(n) time complexity per query, which may not perform well with larger arrays and frequent updates.

Binary Indexed Tree (BIT)

A more efficient approach involves using a Binary Indexed Tree (BIT) to support both updates and range sum queries in O(log n) time. The BIT allows for fast updates and sum calculations by maintaining cumulative sums in a tree-like structure.

Segment Tree

Another approach is to use a Segment Tree, which allows both point updates and range queries in O(log n) time. The Segment Tree divides the array into segments, enabling efficient query and update operations across subarrays.

Complexity Analysis

Metric Value
Time Depends on the final approach
Space Depends on the final approach

The brute force approach results in O(n) time complexity per query. Using a Binary Indexed Tree or Segment Tree reduces the time complexity of both updates and queries to O(log n), making them more suitable for larger datasets with multiple operations.

What Interviewers Usually Probe

  • Can the candidate suggest a more efficient solution than brute force?
  • Does the candidate understand the trade-offs between different data structures like BIT and Segment Tree?
  • How well does the candidate describe optimizing time complexity for both sum queries and updates?

Common Pitfalls or Variants

Common pitfalls

  • Not recognizing that a brute force solution may be too slow for large inputs.
  • Failing to implement efficient update handling in the chosen data structure.
  • Incorrectly managing the data structure’s memory usage, especially with Segment Trees.

Follow-up variants

  • Implementing with a Binary Indexed Tree instead of a Segment Tree.
  • Supporting additional operations like range minimum query alongside sum queries.
  • Optimizing space complexity by adjusting the data structure size or approach.

FAQ

What is the time complexity for range sum queries and updates?

Using a Binary Indexed Tree or Segment Tree, both operations can be handled in O(log n) time. The brute force approach has O(n) time complexity per query.

Can the solution handle large input sizes efficiently?

Yes, using advanced data structures like BIT or Segment Tree can efficiently handle arrays with sizes up to 30,000 and handle up to 30,000 operations.

What is the main challenge in this problem?

The main challenge is to efficiently handle both update and range sum queries on a mutable array, which requires careful selection of data structures.

Is the problem solvable using a simple array?

While an array can store the data, a simple array would be inefficient for range sum queries and updates, leading to slow performance for large inputs.

How does a Binary Indexed Tree work for this problem?

A Binary Indexed Tree stores cumulative sums at various levels, allowing efficient updates and range queries by maintaining partial sums and reducing the need for full array scans.

terminal

Solution

Solution 1

#### Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int):
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x > 0:
            s += self.c[x]
            x -= x & -x
        return s


class NumArray:
    __slots__ = ["tree"]

    def __init__(self, nums: List[int]):
        self.tree = BinaryIndexedTree(len(nums))
        for i, v in enumerate(nums, 1):
            self.tree.update(i, v)

    def update(self, index: int, val: int) -> None:
        prev = self.sumRange(index, index)
        self.tree.update(index + 1, val - prev)

    def sumRange(self, left: int, right: int) -> int:
        return self.tree.query(right + 1) - self.tree.query(left)


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)

Solution 2

#### Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int):
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x > 0:
            s += self.c[x]
            x -= x & -x
        return s


class NumArray:
    __slots__ = ["tree"]

    def __init__(self, nums: List[int]):
        self.tree = BinaryIndexedTree(len(nums))
        for i, v in enumerate(nums, 1):
            self.tree.update(i, v)

    def update(self, index: int, val: int) -> None:
        prev = self.sumRange(index, index)
        self.tree.update(index + 1, val - prev)

    def sumRange(self, left: int, right: int) -> int:
        return self.tree.query(right + 1) - self.tree.query(left)


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)

Continue Practicing

#1157 online majority element in subarray#315 count of smaller numbers after self#327 count of range sum
category

Continue Topic

array

Practice more edge cases under the same topic.

arrow_forwardauto_awesome

Continue Pattern

Array plus Design

Expand the same solving frame across more problems.

arrow_forwardsignal_cellular_alt

Same Difficulty Track

Medium

Stay on this level to stabilize interview delivery.

arrow_forward
Range Sum Query - Mutable Solution: Array plus Design | LeetCode #307 Medium