Range Sum Query - Mutable

MediumDesigndesign

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Build a structure over an integer array that supports both point updates and range-sum queries. - NumArray(nums) initializes the structure with the array nums. - update(index, val) sets nums[index] to val (it replaces the value, it does not add to it). - sumRange(left, right) returns nums[left] + nums[left + 1] + ... + nums[right] for 0 <= left <= right < nums.length. Both update and sumRange should run in O(log n), so that a long mix of the two stays fast.

Examples

Input: ["NumArray","sumRange","update","sumRange","sumRange"] [[[2,4,6]],[0,2],[1,-1],[0,2],[1,1]]
Output: [null,12,null,7,-1]
Initially 2 + 4 + 6 = 12. After setting index 1 to -1 the array is [2,-1,6], which sums to 7; the single-element range [1,1] is -1.
Input: ["NumArray","sumRange","update","sumRange"] [[[5]],[0,0],[0,0],[0,0]]
Output: [null,5,null,0]
A one-element array: the update replaces 5 with 0 (it does not add to it).

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i], val <= 100
  • 0 <= index < nums.length
  • 0 <= left <= right < nums.length
  • At most 3 * 10^4 calls are made to `update` and `sumRange`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More design problems