force_awakens's blog

Persistent Segment trees (number of distinct elements in a subarray)
By force_awakens, history, 8 years ago, In English

hello everyone,

Recently i came across this problem http://www.spoj.com/problems/DQUERY/en/. I coded the offline solution, but i was wondering how to solve it using persisent segment trees.I kept an array last_occur[i] which stores the latest occurence of the number i. now given a range (l,r) we need to find number of distinct elements with last_occur[i] < l.I got stuck here, how do we solve this part?

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

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the problem with doing persistent. We can make seg tree for the last occurunence till r. Now seg tree for last occurence till r+1 will need atmost two updates from previous one . so 2*logn nodes. Now we have built persistent seg tree. we can for query (l,r) do sum query on seg tree of root r.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Suppose lst[i] is the last occurence of a[i], where lst[i] < i.

Now sort the array in increasing order of lst[i] , keeping the initial index, and then iterate through the array and at each iteration update the segment tree by adding 1 to the initial position of the element.

In rt[i] keep the root of the segment tree after updating all the elements for which lst[i] <= i.

Now at each query the answer will be the sum on interval l..r from the segment tree with the root rt[l — 1].

Note that after each update operation on the persistent segment tree, log n nodes will change,therefore the memory complexity is O(n log n)

→ Reply