Range Sum Query - Mutable
Medium · Trees · Array · Design · Binary Indexed Tree · Segment Tree
Problem
Given an integer array nums, support many operations of two kinds: changing one element, and asking for the sum of a contiguous range.
Implement NumArray:
- NumArray(int[] nums) stores the array.
- void update(int index, int val) sets nums[index] to val.
- int sumRange(int left, int right) returns nums[left] + nums[left + 1] + ... + nums[right] (inclusive).
With up to 3 · 10^4 calls mixed in any order, both operations should run in O(log n).
Examples
Input: ops = ["NumArray","sumRange","update","sumRange","sumRange"], args = [[[2,-1,4,3]],[0,3],[1,5],[0,2],[3,3]] Output: [None, 8, None, 11, 3]
The whole array sums to 8. After nums[1] becomes 5, the first three values sum to 2 + 5 + 4 = 11; index 3 alone is 3.
Input: ops = ["NumArray","update","sumRange"], args = [[[7]],[0,-3],[0,0]] Output: [None, None, -3]
The only element becomes -3.
Input: ops = ["NumArray","sumRange","update","sumRange"], args = [[[1,2,3]],[0,2],[2,0],[0,2]] Output: [None, 6, None, 3]
The sum drops from 6 to 3 when the last value becomes 0.
Constraints
- 1 <= len(nums) <= 3 · 10^4
- -100 <= nums[i], val <= 100
- 0 <= index < len(nums)
- 0 <= left <= right < len(nums)
- At most 3 · 10^4 calls to update and sumRange
Approaches
- Baseline: plain array, sum on demand — time update O(1), sumRange O(n), space O(n)
Follow-up
A segment tree does the same in O(log n) and also handles operations without an inverse, such as the minimum; the second use case needs exactly that. The first swaps the roles: range updates and single-value reads, which a Fenwick tree handles over the difference array.
Related problems
Start free on Cariara · Coding problems · System design studio
