Range Sum Query with BIT

Given an array nums, support point updates and range-sum queries using a Fenwick tree. Return the answers for every sum query in order. This is the range-query version of Fenwick tree usage and is a standard alternative to segment trees.

Input Format

nums = initial array, operations = point updates and range sum 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 [1, index, value] for point update or [2, left, right] for range sum query.

Examples

Example 1:

Input:

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

Output:

[9,12]

Explanation:

The first query returns 2+3+4=9. After updating index 2 to 5, the full array sum becomes 12.

Example 2:

Input:

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

Output:

[5,7]

Explanation:

A single element range sum is just the current value at that index.

Loading...
Range Sum Query with BIT - Advanced Trees