Can anybody explain to me how segment trees are used to answer interval stabbing queries? I have searched and searched and only come with the beginning of the line. From my understanding I need to take all the end points of every interval and build a segment tree then what?

How can we know the original intervals now?
How can we check whether a given point is present in any of them and report all those intervals with the point in them?

  • $\begingroup$ en.wikipedia.org/wiki/Segment_tree#Query $\endgroup$ – D.W. Sep 21 '19 at 17:12
  • $\begingroup$ I can't come up with a pseudocode that shows the construction or the querying of the tree. I already read the Wikipedia post. $\endgroup$ – Raafat Abualazm Sep 21 '19 at 18:19
  • $\begingroup$ That part of Wikipedia already contains pseudocode. Where specifically did you get stuck? Where is the first place you got stuck? What do you already understand, and what progress have you made so far? I encourage you to edit your question to make it more focused. $\endgroup$ – D.W. Sep 21 '19 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.