JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Re: Persistent Set (response to post by mukel) | Reply
can anyone please explain @mukel 's solution to DQUERY - D-query Solved by persistent tree.
Re: Persistent Set (response to post by Egor) | Reply
http://www.spoj.pl/problems/DQUERY can be solved using some kind of persistent set, not a persistent balanced search tree but a persistent segment tree, maybe you can find it useful. For this problem there is an offline solution using a Binary Indexed Tree, but with a persistent data structure queries can be answered online.

Code in edit...
Re: Persistent Set (response to post by Egor) | Reply
Thank you!
Re: Persistent Set (response to post by pmachado) | Reply
You can start here. They use red-black trees but I based my implementation on treap
Re: Persistent Set (response to post by Egor) | Reply
Ergor,

Can you give me some reference about this theme?
Re: Persistent Set (response to post by Egor) | Reply
Well, it passed 1st, 2nd and 4th test after I cahnged values of A and B. It seems to have some precision problems, but I believe generally it is correct
Re: Persistent Set (response to post by indy256) | Reply
Code (that do not include my library code, but it all classes/methods used are pretty self explaining) is in edit. It passes sample and last test, I had not run code on any other test through. Will post result when I will run it
Re: Persistent Set (response to post by Egor) | Reply
I think you mean Point location problem.
There was a problem "Mushroom-picking sites" where you were given an arbitrary polygon without self intersections with 100,000 vertices and have to answer 100,000 point location queries (whether a given point belongs to the polygon or doesn't or is on boundary).
here (big archive) are the problem statement and tests: http://www.fpmi.bsu.by/sm.aspx?guid=13856
If this problem is of your interest, please, share you ideas about it.
Re: Persistent Set (response to post by indy256) | Reply
Persistent set is sorted set that also can return any of it's previous states in O(log (number of changes))
Suppose you have some polygons on the plane that do not intersect and have total number of vertices n. You want to be able to answer queries about some point in what polygon it lies. You want to answer this queries in O(log n) worst case time and you do not know all this queries beforehead (e. g. next point will be generated using results of previous calculations)
Re: Persistent Set (response to post by Egor) | Reply
Could you please give an example of such a problem? It will be helpfull, because Persistent Set is not a widely known data structure.
Persistent Set | Reply
Can anyone recommend any problems from online judge/archive with tests that requires persistent set?
RSS