Range Update Point Query

Given an array initially filled with zeros, support adding a value to every element in a range and querying the value at a single index. Return the answers for every point query in order. This is a standard Fenwick tree trick using a difference array.

Input Format

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

Output Format

value at each queried index, in order

Constraints

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

Examples

Example 1:

Input:

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

Output:

[2,2,1]

Explanation:

After the first update, index 2 has value 2. After the second update, index 3 has value 2 and index 0 has value 1.

Example 2:

Input:

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

Output:

[5,5]

Explanation:

Every index gets +5, so both queried positions return 5.

Loading...
Range Update Point Query - Advanced Trees