Latest revision |
Your text |
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==
| + | |
− | 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== | | ==Structure== |
| [[File:Segtree_92631507.png|200px|thumb|right|This segment tree.]] | | [[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,\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: | + | 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: |
| * it is a binary tree which represents some underlying array; | | * 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; | | * 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; |