Persistence Segment Tree

Revision en2, by i_love_emilia_clarke, 2017-04-17 16:11:05

Given an array A of N integers answer Q queries of type (L, R). Answer to a query (L, R) is the sum of distinct integers in the range A[L...R]

Constraints: N, Q <= 100000

0 <= L <= R < N

abs(A[i]) <= 1 000 000 000

I read somewhere that this can be done using persistence segment tree.

So, it would be helpful if one can explain that approach.

Other approach are welcome too.

Tags persistent segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English i_love_emilia_clarke 2017-04-17 16:11:05 5 Tiny change: ' R < N\n\nA[i] <= 1 000 ' -> ' R < N\n\nabs(A[i]) <= 1 000 '
en1 English i_love_emilia_clarke 2017-04-17 16:08:45 413 Initial revision (published)