Talk:Segment tree

Improvement

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. — Preceding unsigned comment added by 201.220.222.140 (talk) 02:13, 21 October 2007 (UTC)

Pending

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) — Preceding unsigned comment added by 201.220.222.140 (talk) 02:13, 21 October 2007 (UTC)

Merge with 'Interval tree'

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.

If I'm not mistaken, the difference is that in the segment tree the structure cannot be modified once built.

Rename

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 would be in favor of the rename. If what's meant by "Segment Tree" differs between the competitive programming world and the computational geometry literature, it makes logical sense to call this article "Segment Tree (computational geometry)". Also, in this UIUC course [2], "Segment Tree" is referred to in the competitive programming sense as well. Quohx (talk) 01:33, 10 March 2022 (UTC)

Introducing an artificial new name for something that is commonly known as "segment tree" (that from competitive computing) is a somewhat strange idea. Obviously (see for instance hit count in google search) this is a common and maybe prevalent usage. The afore mentioned argument for segment tree (computational geometry): "usually meant ... in literature" is very questionable, considering the fact, that the wikipedia article " relies largely or entirely on a single source".

What's wrong with introducing a disambiguation: segment tree (computational geometry) vs. segment tree (competitive programming)?

BTW claiming "In computer science, a segment tree, is ...[the first meaning" is somewhat pretentious. 62.216.204.248 (talk) 21:41, 1 December 2022 (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 74.117.104.6 (talk) 22:16, 27 September 2016 (UTC)

I think that 2800:484:4078:C80:B428:9F02:5F90:D071 (talk) 23:55, 2 October 2021 (UTC)

The Figure isn't correct

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

Querying an interval

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

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

Canonical subset

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

Ambiguity

The lead formerly contained this statement:

Ambiguity - The term segment tree is also widely used in a more abstract sense, where a tree node represents a list of items, and the child nodes represent the sublists.

This seems to be a talk page comment that someone has mistakenly added to the article, so I have moved it here for further discussion. 2601:644:2:B64B:5C17:A04:2533:A462 (talk) 17:20, 14 December 2016 (UTC)

This article is quite obfuscated (as is the sole source). This explains the reported "ambiguity".

I understand the Segment tree described here is basically a 1-dimensional Range tree. Both are attributed to Jon Bentley. Both are build on a list of points ("Consider the partitioning of the real line induced by those points": this is true on a line). The query processes are slightly different because of different questions asked but the query described in Range tree is actually 2 queries in the segment tree. Moreover the article is over complicated by the one-point intervals, only needed in some niche cases.

The segment tree is described here as a solution to the "Stabbing problem" (cited as source). So the nodes accumulate segments. But it can be use more broadly for storing information about intervals. For example, for querying ranged sums in a array the nodes store a partial sum. In this case the answer is an accumulated sum between 2 points/queries (like in Range Tree).

The Interval tree is another beast.

Some other online articles:

• A simple and space efficient segment tree implementation
• Segment Tree

Xavier-gl71 (talk) 10:01, 4 February 2023 (UTC)