Talk:Segment tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.

I'm willing to make this article a featured one. I don't mean as it is right now, of course. I don't know whether this is a naïve goal or not, but anyway I want to do it.


These are some pending issues or problems that should be corrected. I'm willing to do so for many of them; help is always welcome.

  • Things to do to improve the content:
    • Include a drawing of an instance of a segment tree, to illustrate its structure. I was to include the one provided at the book I cite, but I'm afraid of copyright issues. I'm currently working on it.
    • Expand the History section.
    • It would be good to get the original Bentley's publication, to clarify whatever can be clarified, or to expand the article.
  • Minor presentation fixes and pending tasks:
    • See if there are guidelines for writing algorithms or seudocode, and modify the article accordingly.
    • See who is Bentley, who discovered the tree, and possibly add links to an article about him. Seems to be Jon L. Bentley, the article for him is at Jon Bentley.
    • Is the Klee in the History section the same as Victor Klee? If so, perhaps a link could be added in that section.
    • References apparently broken. I'm using them as I read it in the documentation, but it looks like it doesn't work. It would be good if someone could repair them, and/or explain why they don't work.
    • Test and possibly correct all Wikilinks provided; particularly:
      • Union. Is is supposed to refer to the set operation.
    • See if there are some more categories to add to this article.
    • Add links to this article where suitable. It could be useful to look into a good article of some similar data structure to find out this. Some possible candidates could be:
      • Tree (data structure) (I think it has a list of tree-based structures).
      • Computational geometry.
      • Geographic information systems.
      • Bentley's article, if there is one.
    • See if references can be improved in any way, regarding readability. Perhaps they can be more sparse; given that all references are almost the same and there are many contiguous parts referenced. Do this taking into account the guidelines for citing.
    • Analize the possiblity of making some links of mentioned concepts. Particularly:
      • Cost. The article mentions time costs and memory costs.
      • Children. Attempting to open an article about child regarding trees redirects to the trees page. Maybe there is some heading within that article that could be linked with "Children".
      • Parent. If there is no article about this (as I guess), see if it can be linked to some heading within the Tree article.
  • Scientific issues needing clarification:
    • Cost analysis questions: The costs provided for multi-dimensional versions of the tree don't look good to me. However, the paragraph is almost verbatim, and properly located and cited. I would agree with those costs, if they were assuming the use of an interval tree at the last level. Can it be what they ment in the book? It would be good to find more references to define all this.
    • Analyze if it is suitable to make Klee's rectangle problems a link to an article (although such an article still does not exist). What is Klee's rectangle problems?
    • My source claims Single points are treated themselves as intervals because the answer to a query is not necessarily the same at the interior of an elementary interval and its endpoints. Does it mean that the only reason why a node for each endpoint alone exist, is that the query can be open or closed?

Please, check or comment in this page on any fixed issues or modifications to the article. Alfredo J. Herrera Lago 19:11, 21 October 2007 (UTC)

Merge with 'Interval tree'[edit]

How is segment tree is different from interval tree? If they are the same, we should merge these two articles. Andreas Kaufmann (talk) 14:46, 15 March 2009 (UTC)

They have different time/space tradeoffs. Interval trees need less space but queries take longer. Note that the query time for interval trees is given as O(log n + m) in its entry, something that I think is wrong. This has been noted on the discussion page.


There seems to be two data structures going by the name "segment trees". The one described in "Computational Geometry: algorithms and applications", and another one described in [1], and this causes confusion - some interwiki were about the latter data structure. I propose renaming the article to Segment tree (computational geometry). -- X7q (talk) 00:47, 2 May 2010 (UTC)

It appears to me that the type of segment tree discussed here is what is usually meant when the term "segment tree" is used in the literature. I would be in favor of leaving this article as-is and coining a new name for the other type mentioned on the TopCoder tutorial. I think the name "range tree" is appropriate, but apparently that name is already taken. bbi5291 (talk) 22:35, 26 March 2011 (UTC)
I'm partial to the name ARQ (associative range query) Tree to describe the TopCoder structure, though I don't think anyone else uses it. An "arc" is kind of like a segment, so it should be an easy adjustment :) EbTech (talk) 17:10, 18 January 2016 (UTC)

I've been trying to learn about the Topcoder data structure, and the Wikipedia article has confused me greatly. The article now makes some statements referencing that Topcoder tutorial, which is obviously going to be incorrect if the article is really about a different algorithm. At this point, a Google search for "segment tree" returns mostly results pertaining to the Topcoder data structure, as far as I can tell. I agree with naming the article to Segment tree (computational geometry). Waterfalls12 (talk) 05:19, 1 June 2015 (UTC)

I'll add a disambiguation link to Fenwick tree, which appears to be the closest Wikipedia article about the Topcoder segment tree. Waterfalls12 (talk) 02:18, 29 September 2015 (UTC)

Yes, this is very confusing and unfortunate. Before it is fixed, I put in a cautionary paragraph to warn other uninitiated, and link to the google search result page. — Preceding unsigned comment added by (talk) 22:16, 27 September 2016 (UTC)

The Figure isn't correct[edit]

in the figure that demonstrate the tree , There isn't endpoint at the segments while there is point on the line. At Point number 2. — Preceding unsigned comment added by (talk) 17:48, 14 July 2012 (UTC)

Querying an interval[edit]

An important use-case - that of querying an interval with endpoints [qx, qy] has been left out, and it should be noted that the segment tree can answer these queries and report all (k) matches in time O(k log n).

I read the entry on the interval tree, and it is unclear if queries can be answered in time O(k + log n).

OTOH, A balanced binary tree on the left endpoint of the intervals plus fractional cascading on the right endpoint can achieve the optimal O(k + log n) query with O(n log n) space.

Space Complexity[edit]

It is actually possible to implement a segment tree with 2 * N or O(N) space. — Preceding unsigned comment added by (talk) 12:34, 14 November 2012 (UTC)

Canonical subset[edit]

The word canonical is used several times but there is no explanation of it. — Preceding unsigned comment added by (talk) 09:32, 17 March 2016 (UTC)