Prefix Sum Query with Point Update

Given an array and a sequence of operations, support point additions and prefix-sum queries. Return the answers for every prefix query in order. This is a classic Fenwick Tree problem because it maintains prefix sums efficiently under point updates.

Input Format

nums = initial array, operations = point updates and prefix queries

Output Format

prefix sums for every type-2 query, in order

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= operations.length <= 10^5
  • Each operation is [1, index, delta] for add-to-index or [2, index] for prefix query.

Examples

Example 1:

Input:

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

Output:

[6,11,15]

Explanation:

The first prefix up to index 2 is 1+2+3=6. After adding 5 to index 1, the prefix up to 2 becomes 11 and up to 3 becomes 15.

Example 2:

Input:

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

Output:

[5,3]

Explanation:

A single-element prefix is just the current value at index 0.

Loading...
Prefix Sum Query with Point Update