$\begingroup$
$\endgroup$
3
How to create a structure which acts as union of ranges. In that structure new ranges can be inserted beforehand and then some queries are asked to find out if the given point is covered by any of the ranges. What are different approaches and space/time complexity tradeoff?
-
1$\begingroup$ Have you looked at interval trees and segment trees? What research have you done? $\endgroup$D.W.– D.W. ♦2023年12月19日 09:35:41 +00:00Commented Dec 19, 2023 at 9:35
-
$\begingroup$ For segment tree, the range has to be predefined something like -10^5 to 10^5. But I want something which can take ranges from -10^9 to 10^9 which is not efficient with segment trees. $\endgroup$user166204– user1662042023年12月19日 14:13:37 +00:00Commented Dec 19, 2023 at 14:13
-
1$\begingroup$ Please don't put additional information in the comments. Instead, edit your question to describe what approaches you have already considered and why you have rejected them. Make sure that all the requirements are stated clearly in the question. The question doesn't say anything about what ranges a good solution must support, or why you believe a segment tree can only handle -10^5 to 10^5 and cannot handle -10^9 to 10^9, or why you have rejected interval trees. See also cs.stackexchange.com/help/how-to-ask $\endgroup$D.W.– D.W. ♦2023年12月19日 18:00:59 +00:00Commented Dec 19, 2023 at 18:00