Coding questions · Moloco

Support Dynamic Range Sums

This question evaluates knowledge of data structures and algorithmic techniques for range queries and dynamic updates, along with complexity analysis for time and space.

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.

Dynamic Range Sums

Constraints

0 <= left <= right < len(nums)

Examples

Example 1

Input: ([1, 3, 5], [('sum', 0, 2), ('update', 1, 2), ('sum', 0, 2)])
Output: [9, 8]

Explanation: Fenwick update changes range sum.

Example 2

Input: ([0], [('sum', 0, 0), ('update', 0, 7), ('sum', 0, 0)])
Output: [0, 7]

Explanation: Single element.

Hints

A Fenwick tree supports point updates and prefix sums in logarithmic time.