art-hack's blog

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

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


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.


  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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Try persistent segment trees.

4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

Also Please Share the Problem Link here