Support Dynamic Range Sums
Company: Molocoads
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Implement a data structure over an integer array `nums`.
Part 1: If the array never changes, support `sumRange(left, right)` that returns the sum of elements from index `left` to `right`, inclusive.
Part 2 (follow-up): Now the array is mutable. Support both:
- `update(index, value)`: set `nums[index] = value`
- `sumRange(left, right)`: return the inclusive range sum
Design the mutable version so that both operations are efficient when the array length and number of operations can each be up to 100,000. Be prepared to discuss multiple approaches and their tradeoffs.
Quick Answer: This question evaluates knowledge of data structures and algorithmic techniques for range queries and dynamic updates, along with complexity analysis for time and space.
Support update(index,value) and inclusive sumRange queries over an integer array.
Constraints
- 0 <= left <= right < len(nums)
Examples
Input: ([1, 3, 5], [('sum', 0, 2), ('update', 1, 2), ('sum', 0, 2)])
Expected Output: [9, 8]
Explanation: Fenwick update changes range sum.
Input: ([0], [('sum', 0, 0), ('update', 0, 7), ('sum', 0, 0)])
Expected Output: [0, 7]
Explanation: Single element.
Input: ([2, 4, 6], [('sum', 1, 1)])
Expected Output: [4]
Explanation: Single-index range.
Hints
- A Fenwick tree supports point updates and prefix sums in logarithmic time.