Range Update Range Query

Given an array initially filled with zeros, support adding a value to every element in a range and querying the sum of a range. Return the answers for every sum query in order. This is the full range-query version of the Fenwick tree difference technique.

Input Format

n = array length, operations = range adds and range sum queries

Output Format

sum for every type-2 query, in order

Constraints

  • 1 <= n <= 10^5
  • 1 <= operations.length <= 10^5
  • Each operation is [1, left, right, value] for range add or [2, left, right] for range sum query.

Examples

Example 1:

Input:

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

Output:

[6,8]

Explanation:

After the first update, the total sum is 6. After the second update, the sum on indices 1 through 3 becomes 8.

Example 2:

Input:

n = 4
operations = [[1,0,3,5],[2,1,2],[1,1,1,-2],[2,0,3]]

Output:

[10,18]

Explanation:

The first query sees two positions with value 5. After the second update, the total sum becomes 18.

Loading...
Range Update Range Query - Advanced Trees