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

- N<=2*10
^{5} - a
_{i}<= 10^{9} - K <= 10
^{5} - Q <= 10
^{5} - L,R <= N

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

**Example**

Try persistent segment trees.

Why persistent segment tree? Can't we store and rearrange queries and updates in some specific order then solve using segment tree?

Thanks. Didn't see that.

Here's a video I made on a nice introduction to Persistent STs if you want to do it online.

Sir can you reply if https://atcoder.jp/contests/dp/tasks/dp_q this is solved by persistent segment trees only?

Not at all, it just requires a segment tree.

Will check out for sure. Thanks SecondThread

Thanks a lot mraron, that's exactly what I was looking for.

First Take all the Queries and sort them acc to p. Lets say 1<p1<p2<p3....<k. First update sum till pith update stor the answer for 2nd query and then continue updating the Segment Tree. https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

Also Please Share the Problem Link here