Segment tree - Revision history

66.192.186.210: Undo revision 1969 by 66.192.186.210 (talk)

2016-04-06T02:34:57Z

Undo revision 1969 by 66.192.186.210 (talk)

66.192.186.210: /* Implementation */

2016-04-06T02:19:33Z

‎Implementation

Brian: /* Structure */

2011-11-28T14:56:13Z

‎Structure

Brian: /* Structure */ - \left( and \right)

2011-11-28T14:55:26Z

‎Structure: - \left( and \right)

Brian: wikify data structure

2011-06-24T17:42:13Z

wikify data structure

Brian: Reverted edits by 84.16.234.202 (Talk) to last revision by Brian

2010-08-21T17:02:02Z

Reverted edits by 84.16.234.202 (Talk) to last revision by Brian

84.16.234.202: kenny campbell 2c mix 106.5 baltimore http://moblogpuconro.mo.funpic.de/glass-blowing-salso.com.html peddleradvantage.com paris tn forums.on.nimp.org http://moblogpuconro.mo.funpic.de/myway.mail.html

2010-08-21T06:42:52Z

kenny campbell 2c mix 106.5 baltimore http://moblogpuconro.mo.funpic.de/glass-blowing-salso.com.html peddleradvantage.com paris tn forums.on.nimp.org http://moblogpuconro.mo.funpic.de/myway.mail.html

Brian: Reverted edits by 119.252.144.111 (Talk) to last revision by Brian

2010-08-13T05:11:23Z

Reverted edits by 119.252.144.111 (Talk) to last revision by Brian

119.252.144.111: bob.schermerhorn evergreen commons.com http://lanwilftasli.xhost.ro/david-b.-eagan.html www.d.co.il 28867650 www.criss angle magic tricks.com http://lanwilftasli.xhost.ro/saddam.execution-video.html

2010-07-20T23:45:05Z

bob.schermerhorn evergreen commons.com http://lanwilftasli.xhost.ro/david-b.-eagan.html www.d.co.il 28867650 www.criss angle magic tricks.com http://lanwilftasli.xhost.ro/saddam.execution-video.html

Brian: Reverted edits by 193.254.155.110 (Talk) to last revision by Jargon

2010-07-11T14:55:42Z

Reverted edits by 193.254.155.110 (Talk) to last revision by Jargon

@@ Line 80: / Line 80: @@
                      update_rec(2*node+1,mid+1,end,pos,val)
                 A[node] = min(A[2*node],A[2*node+1])
-      private function query_rec(node,a_begin,a_end,s_begin,s_end)
+      private function query_rec(node,t_begin,t_end,a_begin,a_end)
-           if a_begin>=s_begin AND a_end<=s_end
+           if t_begin>=a_begin AND t_end<=a_end
                 return A[node]
            else
-                let mid = floor((a_begin+a_end)/2)
+                let mid = floor((t_begin+t_end)/2)
                 let res = ∞
-                if mid>=s_begin AND a_begin<=s_end
+                if mid>=a_begin AND t_begin<=a_end
-                     res = min(res,query_rec(2*node,a_begin,mid,s_begin,s_end))
+                     res = min(res,query_rec(2*node,t_begin,mid,a_begin,a_end))
-                if a_end>=s_begin AND mid+1<=s_end
+                if t_end>=a_begin AND mid+1<=a_end
-                     res = min(res,query_rec(2*node+1,mid+1,a_end,s_begin,s_end))
+                     res = min(res,query_rec(2*node+1,mid+1,t_end,a_begin,a_end))
                 return res
       function construct(size,a[1..size])
@@ Line 100: / Line 100: @@
            return query_rec(1,1,N,begin,end)
 </pre>
 ==Variations==
 The segment tree can be adapted to retrieve not only the minimum element in a range but also various other functions. Here are some examples taken from otherwise difficult contest problems:

@@ Line 80: / Line 80: @@
                      update_rec(2*node+1,mid+1,end,pos,val)
                 A[node] = min(A[2*node],A[2*node+1])
-      private function query_rec(node,t_begin,t_end,a_begin,a_end)
+      private function query_rec(node,a_begin,a_end,s_begin,s_end)
-           if t_begin>=a_begin AND t_end<=a_end
+           if a_begin>=s_begin AND a_end<=s_end
                 return A[node]
            else
-                let mid = floor((t_begin+t_end)/2)
+                let mid = floor((a_begin+a_end)/2)
                 let res = ∞
-                if mid>=a_begin AND t_begin<=a_end
+                if mid>=s_begin AND a_begin<=s_end
-                     res = min(res,query_rec(2*node,t_begin,mid,a_begin,a_end))
+                     res = min(res,query_rec(2*node,a_begin,mid,s_begin,s_end))
-                if t_end>=a_begin AND mid+1<=a_end
+                if a_end>=s_begin AND mid+1<=s_end
-                     res = min(res,query_rec(2*node+1,mid+1,t_end,a_begin,a_end))
+                     res = min(res,query_rec(2*node+1,mid+1,a_end,s_begin,s_end))
                 return res
       function construct(size,a[1..size])
@@ Line 100: / Line 100: @@
            return query_rec(1,1,N,begin,end)
 </pre>
 ==Variations==
 The segment tree can be adapted to retrieve not only the minimum element in a range but also various other functions. Here are some examples taken from otherwise difficult contest problems:

@@ Line 21: / Line 21: @@
 ==Structure==
 [[File:Segtree_92631507.png|200px|thumb|right|This segment tree.]]
-Suppose that we use the function defined above to evaluate <math>f(1,N)</math>, where <math>N</math> is the number of elements in the array. When <math>N</math> is large, this recursive call has two "children", one of which is the recursive call <math>f\left(1,\lfloor\frac{N+1}{2}\rfloor\right)</math>, and the other one of which is <math>f\left(\lfloor\frac{N+1}{2}\rfloor+1,N\right)</math>. Each of these children will then have two children of its own, and so on, down until the base case is reached. If we represent these recursive calls with a tree structure, the call <math>f(1,N)</math> would be the root, it would have two children, each child would have two more children, and so on; the base cases would be the leaves of the tree. We are now ready to specify the structure of the segment tree:
+Suppose that we use the function defined above to evaluate <math>f(1,N)</math>, where <math>N</math> is the number of elements in the array. When <math>N</math> is large, this recursive call has two "children", one of which is the recursive call <math>f\left(1,\left\lfloor\frac{N+1}{2}\right\rfloor\right)</math>, and the other one of which is <math>f\left(\left\lfloor\frac{N+1}{2}\right\rfloor+1,N\right)</math>. Each of these children will then have two children of its own, and so on, down until the base case is reached. If we represent these recursive calls with a tree structure, the call <math>f(1,N)</math> would be the root, it would have two children, each child would have two more children, and so on; the base cases would be the leaves of the tree. We are now ready to specify the structure of the segment tree:
 * it is a binary tree which represents some underlying array;
 * each node is associated with some interval of the array and contains the value(s) of one or more functions of the elements in that interval;

@@ Line 21: / Line 21: @@
 ==Structure==
 [[File:Segtree_92631507.png|200px|thumb|right|This segment tree.]]
-Suppose that we use the function defined above to evaluate <math>f(1,N)</math>, where <math>N</math> is the number of elements in the array. When <math>N</math> is large, this recursive call has two "children", one of which is the recursive call <math>f(1,\lfloor\frac{N+1}{2}\rfloor)</math>, and the other one of which is <math>f(\lfloor\frac{N+1}{2}\rfloor+1,N)</math>. Each of these children will then have two children of its own, and so on, down until the base case is reached. If we represent these recursive calls with a tree structure, the call <math>f(1,N)</math> would be the root, it would have two children, each child would have two more children, and so on; the base cases would be the leaves of the tree. We are now ready to specify the structure of the segment tree:
+Suppose that we use the function defined above to evaluate <math>f(1,N)</math>, where <math>N</math> is the number of elements in the array. When <math>N</math> is large, this recursive call has two "children", one of which is the recursive call <math>f\left(1,\lfloor\frac{N+1}{2}\rfloor\right)</math>, and the other one of which is <math>f\left(\lfloor\frac{N+1}{2}\rfloor+1,N\right)</math>. Each of these children will then have two children of its own, and so on, down until the base case is reached. If we represent these recursive calls with a tree structure, the call <math>f(1,N)</math> would be the root, it would have two children, each child would have two more children, and so on; the base cases would be the leaves of the tree. We are now ready to specify the structure of the segment tree:
 * it is a binary tree which represents some underlying array;
 * each node is associated with some interval of the array and contains the value(s) of one or more functions of the elements in that interval;

← Older revision		Revision as of 17:42, 24 June 2011
Line 1:		Line 1:
−	The '''segment tree''' is a highly versatile data structure, based upon the [[Divide and conquer\|divide-and-conquer]] paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed.	+	The '''segment tree''' is a highly versatile [[data structure]], based upon the [[Divide and conquer\|divide-and-conquer]] paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed.

	==Motivation==		==Motivation==

@@ Line 1: / Line 1: @@
 The '''segment tree''' is a highly versatile data structure, based upon the [[Divide and conquer|divide-and-conquer]] paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed.
-kenny campbell 2c mix 106.5 baltimore http://moblogpuconro.mo.funpic.de/glass-blowing-salso.com.html peddleradvantage.com paris tn  forums.on.nimp.org http://moblogpuconro.mo.funpic.de/myway.mail.html beeswax.com rubber stamp  florida law section 564.09 http://moblogpuconro.mo.funpic.de/past-ms.-rodeo-america.html john wayne gacy jr  www.bankof america.com worldpoints http://moblogpuconro.mo.funpic.de/lolitampegs.com-home.html auberge.relais.de.reuilly wanadoo.fr  review tamron 28 80mm f 3.5 5.6 http://moblogpuconro.mo.funpic.de/w.a-componon-80mm.html u.s. made shoes.com  i.v.fluids pro http://moblogpuconro.mo.funpic.de/first-night-st.-pete.html arrow delivery.com  rev. luis cortes nueva.org http://moblogpuconro.mo.funpic.de/jerrod-e.-loggins.html antique chairs by h.kroher  advanced auto parts.com http://moblogpuconro.mo.funpic.de/m4b-player.html matsumuras tv asahi.co.jp  www.jennylopez.net index1 en.htm http://moblogpuconro.mo.funpic.de/kanto-kasei-ltd.html www.china.cn  st. augustine cathederal kalamazoo http://moblogpuconro.mo.funpic.de/new-york-info-resources-attractions.ect.html media player 6.4 download
+==Motivation==
 ==Structure==

@@ Line 1: / Line 1: @@
 The '''segment tree''' is a highly versatile data structure, based upon the [[Divide and conquer|divide-and-conquer]] paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed.
-==Motivation==
+kenny campbell 2c mix 106.5 baltimore http://moblogpuconro.mo.funpic.de/glass-blowing-salso.com.html peddleradvantage.com paris tn  forums.on.nimp.org http://moblogpuconro.mo.funpic.de/myway.mail.html beeswax.com rubber stamp  florida law section 564.09 http://moblogpuconro.mo.funpic.de/past-ms.-rodeo-america.html john wayne gacy jr  www.bankof america.com worldpoints http://moblogpuconro.mo.funpic.de/lolitampegs.com-home.html auberge.relais.de.reuilly wanadoo.fr  review tamron 28 80mm f 3.5 5.6 http://moblogpuconro.mo.funpic.de/w.a-componon-80mm.html u.s. made shoes.com  i.v.fluids pro http://moblogpuconro.mo.funpic.de/first-night-st.-pete.html arrow delivery.com  rev. luis cortes nueva.org http://moblogpuconro.mo.funpic.de/jerrod-e.-loggins.html antique chairs by h.kroher  advanced auto parts.com http://moblogpuconro.mo.funpic.de/m4b-player.html matsumuras tv asahi.co.jp  www.jennylopez.net index1 en.htm http://moblogpuconro.mo.funpic.de/kanto-kasei-ltd.html www.china.cn  st. augustine cathederal kalamazoo http://moblogpuconro.mo.funpic.de/new-york-info-resources-attractions.ect.html media player 6.4 download
-One of the most common applications of the segment tree is the solution to the [[range minimum query]] problem. In this problem, we are given some array and repeatedly asked to find the minimum value within some specified range of indices. For example, if we are given the array <math>[9,2,6,3,1,5,0,7]</math>, we might be asked for the minimum element between the third and the sixth, inclusive, which would be <math>\min(6,3,1,5) = 1</math>. Then, another query might ask for the minimum element between the first and third, inclusive, and we would answer 2, and so on. Various solutions to this problem are discussed in the [[range minimum query]] article, but the segment tree is often the most appropriate choice, especially when modification instructions are interspersed with the queries. For the sake of brevity, we shall focus for several following sections on the type of segment tree designed to answer the range minimum query without explicitly re-stating each time that we are doing so. Bear in mind, however, that other types of segment tree exist, which are discussed later in the article.
-−
-===The divide-and-conquer solution===
-The divide-and-conquer solution would be as follows:
-* If the range contains one element, that element itself is trivially the minimum within that range.
-* Otherwise, divide the range into two smaller ranges, each approximately half the size of the original, and find their respective minima. The minimum for the original range is then the smaller of the two minima of the sub-ranges.
-Hence, if <math>a_i</math> denotes the <math>i</math><sup>th</sup> element in the array, finding the minimum could be encoded as the following recursive function:
-:<math>\displaystyle
-f(x,y) =
-\begin{cases}
-a_x & \mathrm{if\ } x = y \\
-\min(f(x,\lfloor\frac{x+y}{2}\rfloor),f(\lfloor\frac{x+y}{2}\rfloor+1,y)) & \mathrm{otherwise} \\
-\end{cases}
-</math>
-assuming that <math>x \le y</math>.<br/>
-Hence, for example, the first query from the previous section would be <math>f(3,6)</math> and it would be recursively evaluated as <math>\min(f(3,4),f(5,6))</math>.
 ==Structure==