![]() | This article has not yet been rated on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
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)
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.
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)
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.
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)
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)
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)
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)
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.
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)
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)
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 has not yet been rated on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
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)
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.
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)
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.
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)
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)
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)
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)
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.
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)
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)
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)