/307. Range Sum Query - Mutable
Previous|Next

307. Range Sum Query - Mutable

Medium
Arrays42.7% acceptance

Implement a class DynamicArraySum that supports the following operations on an integer array:

1. Initialization with an integer array data.

2. update(position, new_value): Update the element at index position to new_value.

3. sum_interval(start, end): Return the sum of elements from index start to end (inclusive).

The operations may be called multiple times in any order.

Example 1

Input: ["DynamicArraySum", "sum_interval", "update", "sum_interval"] [[[4, -2, 7, 1]], [1, 3], [2, 5], [0, 2]]

Output: [null, 6, null, 7]

Explanation: DynamicArraySum([4, -2, 7, 1]) creates the array. sum_interval(1, 3) returns -2 + 7 + 1 = 6. update(2, 5) changes array to [4, -2, 5, 1]. sum_interval(0, 2) returns 4 + (-2) + 5 = 7.

Example 2

Input: ["DynamicArraySum", "update", "sum_interval", "update", "sum_interval"] [[[-5, 0, 8, 3]], [0, 10], [0, 3], [3, -2], [1, 3]]

Output: [null, null, 21, null, 6]

Explanation: DynamicArraySum([-5, 0, 8, 3]) creates the array. update(0, 10) changes array to [10, 0, 8, 3]. sum_interval(0, 3) returns 10 + 0 + 8 + 3 = 21. update(3, -2) changes array to [10, 0, 8, -2]. sum_interval(1, 3) returns 0 + 8 + (-2) = 6.

Constraints

  • 1 <= len(data) <= 30000
  • -100 <= data[i] <= 100
  • 0 <= position < len(data)
  • -100 <= new_value <= 100
  • 0 <= start <= end < len(data)
  • At most 30000 calls to update and sum_interval
Python (current runtime)

Case 1

Input: ["DynamicArraySum", "sum_interval", "update", "sum_interval"] [[[9, 2, -3, 6]], [0, 1], [3, 0], [2, 3]]

Expected: [null, 11, null, 3]

Case 2

Input: ["DynamicArraySum", "update", "sum_interval", "update", "sum_interval"] [[[5, 5, 5, 5]], [1, 10], [0, 2], [2, -5], [1, 3]]

Expected: [null, null, 20, null, 10]