Hey Everyone, I am trying to solve a problem and got stuck at this subproblem.

Problem

You are given an initial array a with N elements.

There are a series of update operations, Let's say there are K operation, such that in each operation a_i is replaced with x_i.

Now there are Q range sum queries, and in each query, you're given L, R, and P.

You have to find the sum of range in [L, R] after the p^th update has occurred.

Constraints

1. N<=2*10⁵
2. a_i <= 10⁹
3. K <= 10⁵
4. Q <= 10⁵
5. L,R <= N

The solution should preferably be with preprocessing and not be with offline queries.

Initial array [1, 2, 3, 4, 5]
Updates (K=3):
(Index ReplacedValue)
0 5
1 4
2 4
Queries(Q=3)
0 4 1
1 3 2
1 4 0

Answer:
21 (5+4+3+4+5)
11 (4+4+3)
14 (2+3+4+5)