Range Sum Query with Point Update

Given an array nums, support two operations on a mutable array: update a single index to a new value, and query the sum of any subarray. Return the answers for every range-sum query in order. This is a classic segment tree problem because it needs both fast point updates and fast range aggregation.

Input Format

nums = initial integer array, operations = sequence of updates and queries

Output Format

sum for every type-2 query, in order

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= operations.length <= 10^5
  • Each operation is either [1, index, value] for point update or [2, left, right] for range sum query.

Examples

Example 1:

Input:

nums = [1,3,5]
operations = [[2,0,2],[1,1,2],[2,0,2]]

Output:

[9,8]

Explanation:

The first query returns 1+3+5=9. After updating index 1 to 2, the array becomes [1,2,5], so the next query returns 8.

Example 2:

Input:

nums = [2,4,6,8]
operations = [[2,1,3],[1,2,10],[2,0,3]]

Output:

[18,24]

Explanation:

The first query sums 4+6+8=18. After the update, the whole array sums to 24.

Loading...
Range Sum Query with Point Update