Data Structures19 sections · 729 units
Open in Course

Problem - Range Sum Query Mutable

Classic application

Given an integer array nums, implement:

  • update(index, val): Update nums[index] to val
  • sumRange(left, right): Return the sum of elements from left to right inclusive Example:
nums = [1, 3, 5]
sumRange(0, 2) → 9
update(1, 2)
sumRange(0, 2) → 8
``` You're solving the textbook segment tree application. 

Both operations must be efficient. Constraints: up to $3 \cdot 10^4$ elements, up to $3 \cdot 10^4$ operations.