Tag Info

New answers tagged search-trees

1

Since there are no updates there is a rather simple solution. Store a map of key -> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position. For example in the input array: [(3, 1), (2, 3), ...

0

Since you have specified that the array is unsorted, i am afraid you cant do a query in $O(logN)$, assuming we are talking about time complexity and not space complexity (but i think this is the case since you have expressed the desire to make the query efficient because there can be more than one). Keep in mind that (apart from a few exceptions which ...

5

(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case). Consider ...

Top 50 recent answers are included