Design a data structure that supports the following two operations on
a set S of integers:
a. Insert(x; S), which inserts element x into set S, and
b. DeleteLargerHalf(S), which deletes the largest ceil(|S|/2) elements
from S.
Show how to implement this data structure so both operations take O(1)
a
Hi,
There are n points in a plane (p1,p2 pn). Design a O(N2) data structure
so as to answer the querry
"How many points are there in this rectangle" in O(1) time
The rectangle will be specified by the lower left point and upper right
point.
Thanks,
Raghavendra
--~--~-~--~~--
