Range Sum Query - Mutable

You are given an initial integer array nums plus three parallel arrays describing operations to perform from left to right.

At index i:

• if operations[i] == "update", set nums[first[i]] = second[i];
• if operations[i] == "sumRange", append the sum of nums[first[i]..second[i]] (inclusive) to the answer.

Return the list of outputs produced by all sumRange operations.

Input / output

• Input: nums: int[], operations: string[], first: int[], second: int[]
• Output: int[] containing every query result in order

Examples

1. nums = [1,3,5], operations = ["sumRange","update","sumRange"], first = [0,1,0], second = [2,2,2] returns [9,8].
2. nums = [7], operations = ["sumRange","update","sumRange"], first = [0,0,0], second = [0,-1,0] returns [7,-1].
3. nums = [2,4,6,8], operations = ["sumRange","update","sumRange","update","sumRange"], first = [1,2,1,0,0], second = [3,10,3,5,2] returns [18,22,19].

Constraints

• 1 <= nums.length <= 3 * 10^4
• 1 <= operations.length == first.length == second.length <= 3 * 10^4
• operations[i] is either "update" or "sumRange"
• 0 <= first[i], second[i] < nums.length for sumRange operations with first[i] <= second[i]
• 0 <= first[i] < nums.length for update operations

Target complexity

• Aim for O(log n) per update/query after O(n log n) or better preprocessing.

Hints

1. A prefix-sum array answers queries quickly, but a single update would force many entries to change.
2. A Fenwick tree stores partial sums so both point updates and prefix queries stay logarithmic.

Follow-up When would a segment tree be preferable to a Fenwick tree for this family of range-query problems?