Range Sum Queries after Updates

Правка en1, от art-hack, 2020-07-07 21:36:50

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
Теги #range query

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский art-hack 2020-07-07 21:36:50 1001 Initial revision (published)