art-hack's blog

Range Sum Queries after Updates
By art-hack, history, 4 years ago, In English

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
  • Vote: I like it
  • +11
  • Vote: I do not like it

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

Try persistent segment trees.

→ Reply
»
4 years 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. https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

Also Please Share the Problem Link here

→ Reply