DSA problem
Range Sum Query - Mutable
Given an integer array nums, handle multiple queries of the following types: update the value at a given index, and compute the sum of elements in an arbitrary range [left, right]. Implement the NumArray class supporting update(index, val) and sumRange(left, right).
A naive approach stores the array as-is. update is O(1) but sumRange is O(n) per call. The reverse extreme keeps a prefix-sum array: sumRange is O(1) but every update requires rebuilding the suffix, costing O(n). With many of each operation mixed together, both extremes degrade to O(n) per call on average.
The Fenwick tree (Binary Indexed Tree, BIT) is the textbook fix. It is a one-dimensional array indexed from 1 to n in which each cell tree[i] stores a partial sum over a power-of-two-sized range determined by the lowest set bit of i. The clever bit-manipulation identity i & -i extracts that lowest set bit, letting us walk up the tree on updates (adding the lowest bit) and walk down on prefix queries (subtracting the lowest bit).
The optimal design supports both operations in O(log n) time using O(n) extra memory. The class stores the original nums (to compute the delta when overwriting an index) plus a BIT of size n + 1. update(i, val) translates to bitUpdate(i + 1, val - nums[i]); sumRange(l, r) is prefix(r + 1) - prefix(l). This is the canonical solution interviewers expect.
Examples
["NumArray","sumRange","update","sumRange"]
[[[1,3,5]],[0,2],[1,2],[0,2]][null,9,null,8]["NumArray","update","sumRange","update","sumRange"]
[[[7,2,7,2,0]],[4,6],[0,4],[0,3],[0,4]][null,null,24,null,20]["NumArray","sumRange"]
[[[1]],[0,0]][null,1]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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.