### art-hack's blog

By art-hack, history, 4 weeks ago, ,

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 ai is replaced with xi.

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 pth update has occurred.

### Constraints

1. N<=2*105
2. ai <= 109
3. K <= 105
4. Q <= 105
5. L,R <= N

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

Example

• +11

 » 4 weeks ago, # |   +20 Try persistent segment trees.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +7 Why persistent segment tree? Can't we store and rearrange queries and updates in some specific order then solve using segment tree?
•  » » » 4 weeks ago, # ^ |   +6 'The solution should (...) not be with offline queries.'
•  » » » » 4 weeks ago, # ^ |   +6 Thanks. Didn't see that.
•  » » 4 weeks ago, # ^ |   +10 Here's a video I made on a nice introduction to Persistent STs if you want to do it online.
•  » » » 4 weeks ago, # ^ |   0 Sir can you reply if https://atcoder.jp/contests/dp/tasks/dp_q this is solved by persistent segment trees only?
•  » » » » 4 weeks ago, # ^ |   0 Not at all, it just requires a segment tree.
•  » » » 4 weeks ago, # ^ |   0 Will check out for sure. Thanks SecondThread
•  » » 4 weeks ago, # ^ |   +8 Thanks a lot mraron, that's exactly what I was looking for.
 » 4 weeks ago, # |   0 First Take all the Queries and sort them acc to p. Lets say 1