Efficient solution to add / sum problem

Revision en1, by oversolver, 2018-12-14 16:26:08

We have n points (xi, yi). Let both x and y be different and from [1, n].

Initially, all points have zero value.

Two types of queries:

1) add X — adding +1 to all points with xi ≤ X

2) sum Y — calculate sum of values of points with yi ≤ Y

What is best known solution? (Problem not from running contest).

Tags queries, data structures, inversions

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English oversolver 2018-12-14 16:26:08 392 Initial revision (published)