http://wcipeg.com/wiki/index.php?title=Segment_tree&feed=atom&action=history
Segment tree - Revision history
2024-03-29T08:54:32Z
Revision history for this page on the wiki
MediaWiki 1.25.2
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=1970&oldid=prev
66.192.186.210: Undo revision 1969 by 66.192.186.210 (talk)
2016-04-06T02:34:57Z
<p>Undo revision 1969 by <a href="/wiki/Special:Contributions/66.192.186.210" title="Special:Contributions/66.192.186.210">66.192.186.210</a> (<a href="/wiki/index.php?title=User_talk:66.192.186.210&action=edit&redlink=1" class="new" title="User talk:66.192.186.210 (page does not exist)">talk</a>)</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 02:34, 6 April 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L80" >Line 80:</td>
<td colspan="2" class="diff-lineno">Line 80:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>                     update_rec(2*node+1,mid+1,end,pos,val)</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>                     update_rec(2*node+1,mid+1,end,pos,val)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               A[node] = min(A[2*node],A[2*node+1])</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               A[node] = min(A[2*node],A[2*node+1])</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>     private function query_rec(node,<del class="diffchange diffchange-inline">a_begin</del>,<del class="diffchange diffchange-inline">a_end</del>,<del class="diffchange diffchange-inline">s_begin</del>,<del class="diffchange diffchange-inline">s_end</del>)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>     private function query_rec(node,<ins class="diffchange diffchange-inline">t_begin</ins>,<ins class="diffchange diffchange-inline">t_end</ins>,<ins class="diffchange diffchange-inline">a_begin</ins>,<ins class="diffchange diffchange-inline">a_end</ins>)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>           if <del class="diffchange diffchange-inline">a_begin</del>>=<del class="diffchange diffchange-inline">s_begin </del>AND <del class="diffchange diffchange-inline">a_end</del><=<del class="diffchange diffchange-inline">s_end</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>           if <ins class="diffchange diffchange-inline">t_begin</ins>>=<ins class="diffchange diffchange-inline">a_begin </ins>AND <ins class="diffchange diffchange-inline">t_end</ins><=<ins class="diffchange diffchange-inline">a_end</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return A[node]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return A[node]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           else</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           else</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>               let mid = floor((<del class="diffchange diffchange-inline">a_begin</del>+<del class="diffchange diffchange-inline">a_end</del>)/2)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>               let mid = floor((<ins class="diffchange diffchange-inline">t_begin</ins>+<ins class="diffchange diffchange-inline">t_end</ins>)/2)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               let res = ∞</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               let res = ∞</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>               if mid>=<del class="diffchange diffchange-inline">s_begin AND </del>a_begin<=<del class="diffchange diffchange-inline">s_end</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>               if mid>=a_begin <ins class="diffchange diffchange-inline">AND t_begin</ins><=<ins class="diffchange diffchange-inline">a_end</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node,<del class="diffchange diffchange-inline">a_begin</del>,mid,<del class="diffchange diffchange-inline">s_begin</del>,<del class="diffchange diffchange-inline">s_end</del>))</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node,<ins class="diffchange diffchange-inline">t_begin</ins>,mid,<ins class="diffchange diffchange-inline">a_begin</ins>,<ins class="diffchange diffchange-inline">a_end</ins>))</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>               if <del class="diffchange diffchange-inline">a_end</del>>=<del class="diffchange diffchange-inline">s_begin </del>AND mid+1<=<del class="diffchange diffchange-inline">s_end</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>               if <ins class="diffchange diffchange-inline">t_end</ins>>=<ins class="diffchange diffchange-inline">a_begin </ins>AND mid+1<=<ins class="diffchange diffchange-inline">a_end</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node+1,mid+1,<del class="diffchange diffchange-inline">a_end</del>,<del class="diffchange diffchange-inline">s_begin</del>,<del class="diffchange diffchange-inline">s_end</del>))</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node+1,mid+1,<ins class="diffchange diffchange-inline">t_end</ins>,<ins class="diffchange diffchange-inline">a_begin</ins>,<ins class="diffchange diffchange-inline">a_end</ins>))</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return res</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return res</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct(size,a[1..size])</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct(size,a[1..size])</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="L100" >Line 100:</td>
<td colspan="2" class="diff-lineno">Line 100:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return query_rec(1,1,N,begin,end)</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return query_rec(1,1,N,begin,end)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></pre></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></pre></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Variations==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Variations==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td></tr>
</table>
66.192.186.210
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=1969&oldid=prev
66.192.186.210: /* Implementation */
2016-04-06T02:19:33Z
<p><span dir="auto"><span class="autocomment">Implementation</span></span></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 02:19, 6 April 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L80" >Line 80:</td>
<td colspan="2" class="diff-lineno">Line 80:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>                     update_rec(2*node+1,mid+1,end,pos,val)</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>                     update_rec(2*node+1,mid+1,end,pos,val)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               A[node] = min(A[2*node],A[2*node+1])</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               A[node] = min(A[2*node],A[2*node+1])</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>     private function query_rec(node<del class="diffchange diffchange-inline">,t_begin,t_end</del>,a_begin,a_end)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>     private function query_rec(node,a_begin,a_end<ins class="diffchange diffchange-inline">,s_begin,s_end</ins>)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>           if <del class="diffchange diffchange-inline">t_begin</del>>=<del class="diffchange diffchange-inline">a_begin </del>AND <del class="diffchange diffchange-inline">t_end</del><=<del class="diffchange diffchange-inline">a_end</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>           if <ins class="diffchange diffchange-inline">a_begin</ins>>=<ins class="diffchange diffchange-inline">s_begin </ins>AND <ins class="diffchange diffchange-inline">a_end</ins><=<ins class="diffchange diffchange-inline">s_end</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return A[node]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return A[node]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           else</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           else</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>               let mid = floor((<del class="diffchange diffchange-inline">t_begin</del>+<del class="diffchange diffchange-inline">t_end</del>)/2)</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>               let mid = floor((<ins class="diffchange diffchange-inline">a_begin</ins>+<ins class="diffchange diffchange-inline">a_end</ins>)/2)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               let res = ∞</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               let res = ∞</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>               if mid>=a_begin <del class="diffchange diffchange-inline">AND t_begin</del><=<del class="diffchange diffchange-inline">a_end</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>               if mid>=<ins class="diffchange diffchange-inline">s_begin AND </ins>a_begin<=<ins class="diffchange diffchange-inline">s_end</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node,<del class="diffchange diffchange-inline">t_begin</del>,mid,<del class="diffchange diffchange-inline">a_begin</del>,<del class="diffchange diffchange-inline">a_end</del>))</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node,<ins class="diffchange diffchange-inline">a_begin</ins>,mid,<ins class="diffchange diffchange-inline">s_begin</ins>,<ins class="diffchange diffchange-inline">s_end</ins>))</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>               if <del class="diffchange diffchange-inline">t_end</del>>=<del class="diffchange diffchange-inline">a_begin </del>AND mid+1<=<del class="diffchange diffchange-inline">a_end</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>               if <ins class="diffchange diffchange-inline">a_end</ins>>=<ins class="diffchange diffchange-inline">s_begin </ins>AND mid+1<=<ins class="diffchange diffchange-inline">s_end</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node+1,mid+1,<del class="diffchange diffchange-inline">t_end</del>,<del class="diffchange diffchange-inline">a_begin</del>,<del class="diffchange diffchange-inline">a_end</del>))</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>                     res = min(res,query_rec(2*node+1,mid+1,<ins class="diffchange diffchange-inline">a_end</ins>,<ins class="diffchange diffchange-inline">s_begin</ins>,<ins class="diffchange diffchange-inline">s_end</ins>))</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return res</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>               return res</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct(size,a[1..size])</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>     function construct(size,a[1..size])</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="L100" >Line 100:</td>
<td colspan="2" class="diff-lineno">Line 100:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return query_rec(1,1,N,begin,end)</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>           return query_rec(1,1,N,begin,end)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></pre></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></pre></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Variations==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Variations==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td></tr>
</table>
66.192.186.210
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=1454&oldid=prev
Brian: /* Structure */
2011-11-28T14:56:13Z
<p><span dir="auto"><span class="autocomment">Structure</span></span></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 14:56, 28 November 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L21" >Line 21:</td>
<td colspan="2" class="diff-lineno">Line 21:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[File:Segtree_92631507.png|200px|thumb|right|This segment tree.]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[File:Segtree_92631507.png|200px|thumb|right|This segment tree.]]</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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,<ins class="diffchange diffchange-inline">\left</ins>\lfloor\frac{N+1}{2}<ins class="diffchange diffchange-inline">\right</ins>\rfloor\right)</math>, and the other one of which is <math>f\left(<ins class="diffchange diffchange-inline">\left</ins>\lfloor\frac{N+1}{2}<ins class="diffchange diffchange-inline">\right</ins>\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:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* it is a binary tree which represents some underlying array;</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* it is a binary tree which represents some underlying array;</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* 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;</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* 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;</div></td></tr>
</table>
Brian
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=1453&oldid=prev
Brian: /* Structure */ - \left( and \right)
2011-11-28T14:55:26Z
<p><span dir="auto"><span class="autocomment">Structure: </span> - \left( and \right)</span></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 14:55, 28 November 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L21" >Line 21:</td>
<td colspan="2" class="diff-lineno">Line 21:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[File:Segtree_92631507.png|200px|thumb|right|This segment tree.]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[File:Segtree_92631507.png|200px|thumb|right|This segment tree.]]</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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:</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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<ins class="diffchange diffchange-inline">\left</ins>(1,\lfloor\frac{N+1}{2}\rfloor<ins class="diffchange diffchange-inline">\right</ins>)</math>, and the other one of which is <math>f<ins class="diffchange diffchange-inline">\left</ins>(\lfloor\frac{N+1}{2}\rfloor+1,N<ins class="diffchange diffchange-inline">\right</ins>)</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:</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* it is a binary tree which represents some underlying array;</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* it is a binary tree which represents some underlying array;</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* 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;</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* 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;</div></td></tr>
</table>
Brian
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=1364&oldid=prev
Brian: wikify data structure
2011-06-24T17:42:13Z
<p>wikify data structure</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:42, 24 June 2011</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The '''segment tree''' is a highly versatile <ins class="diffchange diffchange-inline">[[</ins>data structure<ins class="diffchange diffchange-inline">]]</ins>, 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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Motivation==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Motivation==</div></td></tr>
</table>
Brian
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=439&oldid=prev
Brian: Reverted edits by 84.16.234.202 (Talk) to last revision by Brian
2010-08-21T17:02:02Z
<p>Reverted edits by <a href="/wiki/Special:Contributions/84.16.234.202" title="Special:Contributions/84.16.234.202">84.16.234.202</a> (<a href="/wiki/index.php?title=User_talk:84.16.234.202&action=edit&redlink=1" class="new" title="User talk:84.16.234.202 (page does not exist)">Talk</a>) to last revision by <a href="/wiki/User:Brian" title="User:Brian">Brian</a></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 17:02, 21 August 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">kenny campbell 2c mix 106</del>.5 <del class="diffchange diffchange-inline">baltimore http:</del>//<del class="diffchange diffchange-inline">moblogpuconro</del>.<del class="diffchange diffchange-inline">mo</del>.<del class="diffchange diffchange-inline">funpic</del>.<del class="diffchange diffchange-inline">de/glass</del>-<del class="diffchange diffchange-inline">blowing-salso</del>.<del class="diffchange diffchange-inline">com</del>.<del class="diffchange diffchange-inline">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</del>-<del class="diffchange diffchange-inline">ms.</del>-<del class="diffchange diffchange-inline">rodeo</del>-<del class="diffchange diffchange-inline">america.html john wayne gacy jr  www.bankof america.com worldpoints http</del>:<del class="diffchange diffchange-inline">//moblogpuconro</del>.<del class="diffchange diffchange-inline">mo.funpic.de/lolitampegs</del>.<del class="diffchange diffchange-inline">com</del>-<del class="diffchange diffchange-inline">home</del>.<del class="diffchange diffchange-inline">html auberge.relais.de.reuilly wanadoo.fr  review tamron 28 80mm f 3.5 5.6 http:</del>/<del class="diffchange diffchange-inline">/moblogpuconro.mo.funpic.de/w.a-componon-80mm.html u.s. made shoes.com  </del>i<del class="diffchange diffchange-inline">.v.fluids pro http:</del>//<del class="diffchange diffchange-inline">moblogpuconro.mo.funpic.de/first-night-st.-pete.html arrow delivery.com  rev. luis cortes nueva.org http</del>:<del class="diffchange diffchange-inline">//moblogpuconro.mo.funpic.de/jerrod-e.-loggins.html antique chairs by h.kroher  advanced auto parts.com http</del>://<del class="diffchange diffchange-inline">moblogpuconro</del>.<del class="diffchange diffchange-inline">mo.funpic.de</del>/<del class="diffchange diffchange-inline">m4b-player.html matsumuras tv asahi.co.jp  www.jennylopez.net index1 en.htm http:</del>//<del class="diffchange diffchange-inline">moblogpuconro</del>.<del class="diffchange diffchange-inline">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</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">==Motivation==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">One of the most common applications of the segment tree is the solution to the [[range minimum query]] problem</ins>. <ins class="diffchange diffchange-inline">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,</ins>5<ins class="diffchange diffchange-inline">,0,7]<</ins>/<ins class="diffchange diffchange-inline">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<</ins>/<ins class="diffchange diffchange-inline">math></ins>. <ins class="diffchange diffchange-inline">Then, another query might ask for the minimum element between the first and third, inclusive, and we would answer 2, and so on</ins>. <ins class="diffchange diffchange-inline">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</ins>. <ins class="diffchange diffchange-inline">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</ins>-<ins class="diffchange diffchange-inline">stating each time that we are doing so</ins>. <ins class="diffchange diffchange-inline">Bear in mind, however, that other types of segment tree exist, which are discussed later in the article</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">===The divide</ins>-<ins class="diffchange diffchange-inline">and</ins>-<ins class="diffchange diffchange-inline">conquer solution===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">The divide</ins>-<ins class="diffchange diffchange-inline">and-conquer solution would be as follows</ins>:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* If the range contains one element, that element itself is trivially the minimum within that range</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* Otherwise, divide the range into two smaller ranges, each approximately half the size of the original, and find their respective minima</ins>. <ins class="diffchange diffchange-inline">The minimum for the original range is then the smaller of the two minima of the sub</ins>-<ins class="diffchange diffchange-inline">ranges</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Hence, if <math>a_i<</ins>/<ins class="diffchange diffchange-inline">math> denotes the <math></ins>i<ins class="diffchange diffchange-inline"><</ins>/<ins class="diffchange diffchange-inline">math><sup>th<</ins>/<ins class="diffchange diffchange-inline">sup> element in the array, finding the minimum could be encoded as the following recursive function</ins>:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<ins class="diffchange diffchange-inline"><math>\displaystyle</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">f(x,y) =</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\begin{cases}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">a_x & \mathrm{if\ } x = y \\</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\min(f(x,\lfloor\frac{x+y}{2}\rfloor),f(\lfloor\frac{x+y}{2}\rfloor+1,y)) & \mathrm{otherwise} \\</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\end{cases}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><</ins>/<ins class="diffchange diffchange-inline">math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">assuming that <math>x \le y<</ins>/<ins class="diffchange diffchange-inline">math></ins>.<ins class="diffchange diffchange-inline"><br</ins>/<ins class="diffchange diffchange-inline">></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Hence, for example, the first query from the previous section would be <math>f(3,6)<</ins>/<ins class="diffchange diffchange-inline">math> and it would be recursively evaluated as <math>\min(f(3,4),f(5,6))<</ins>/<ins class="diffchange diffchange-inline">math></ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td></tr>
</table>
Brian
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=438&oldid=prev
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
<p>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</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 06:42, 21 August 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">==Motivation==</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">kenny campbell 2c mix 106</ins>.5 <ins class="diffchange diffchange-inline">baltimore http:</ins>//<ins class="diffchange diffchange-inline">moblogpuconro</ins>.<ins class="diffchange diffchange-inline">mo</ins>.<ins class="diffchange diffchange-inline">funpic</ins>.<ins class="diffchange diffchange-inline">de/glass</ins>-<ins class="diffchange diffchange-inline">blowing-salso</ins>.<ins class="diffchange diffchange-inline">com</ins>.<ins class="diffchange diffchange-inline">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</ins>-<ins class="diffchange diffchange-inline">ms.</ins>-<ins class="diffchange diffchange-inline">rodeo</ins>-<ins class="diffchange diffchange-inline">america.html john wayne gacy jr  www.bankof america.com worldpoints http</ins>:<ins class="diffchange diffchange-inline">//moblogpuconro</ins>.<ins class="diffchange diffchange-inline">mo.funpic.de/lolitampegs</ins>.<ins class="diffchange diffchange-inline">com</ins>-<ins class="diffchange diffchange-inline">home</ins>.<ins class="diffchange diffchange-inline">html auberge.relais.de.reuilly wanadoo.fr  review tamron 28 80mm f 3.5 5.6 http:</ins>/<ins class="diffchange diffchange-inline">/moblogpuconro.mo.funpic.de/w.a-componon-80mm.html u.s. made shoes.com  </ins>i<ins class="diffchange diffchange-inline">.v.fluids pro http:</ins>//<ins class="diffchange diffchange-inline">moblogpuconro.mo.funpic.de/first-night-st.-pete.html arrow delivery.com  rev. luis cortes nueva.org http</ins>:<ins class="diffchange diffchange-inline">//moblogpuconro.mo.funpic.de/jerrod-e.-loggins.html antique chairs by h.kroher  advanced auto parts.com http</ins>://<ins class="diffchange diffchange-inline">moblogpuconro</ins>.<ins class="diffchange diffchange-inline">mo.funpic.de</ins>/<ins class="diffchange diffchange-inline">m4b-player.html matsumuras tv asahi.co.jp  www.jennylopez.net index1 en.htm http:</ins>//<ins class="diffchange diffchange-inline">moblogpuconro</ins>.<ins class="diffchange diffchange-inline">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</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">One of the most common applications of the segment tree is the solution to the [[range minimum query]] problem</del>. <del class="diffchange diffchange-inline">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,</del>5<del class="diffchange diffchange-inline">,0,7]<</del>/<del class="diffchange diffchange-inline">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<</del>/<del class="diffchange diffchange-inline">math></del>. <del class="diffchange diffchange-inline">Then, another query might ask for the minimum element between the first and third, inclusive, and we would answer 2, and so on</del>. <del class="diffchange diffchange-inline">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</del>. <del class="diffchange diffchange-inline">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</del>-<del class="diffchange diffchange-inline">stating each time that we are doing so</del>. <del class="diffchange diffchange-inline">Bear in mind, however, that other types of segment tree exist, which are discussed later in the article</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">===The divide</del>-<del class="diffchange diffchange-inline">and</del>-<del class="diffchange diffchange-inline">conquer solution===</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">The divide</del>-<del class="diffchange diffchange-inline">and-conquer solution would be as follows</del>:</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* If the range contains one element, that element itself is trivially the minimum within that range</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* Otherwise, divide the range into two smaller ranges, each approximately half the size of the original, and find their respective minima</del>. <del class="diffchange diffchange-inline">The minimum for the original range is then the smaller of the two minima of the sub</del>-<del class="diffchange diffchange-inline">ranges</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Hence, if <math>a_i<</del>/<del class="diffchange diffchange-inline">math> denotes the <math></del>i<del class="diffchange diffchange-inline"><</del>/<del class="diffchange diffchange-inline">math><sup>th<</del>/<del class="diffchange diffchange-inline">sup> element in the array, finding the minimum could be encoded as the following recursive function</del>:</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:<del class="diffchange diffchange-inline"><math>\displaystyle</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">f(x,y) =</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\begin{cases}</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">a_x & \mathrm{if\ } x = y \\</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\min(f(x,\lfloor\frac{x+y}{2}\rfloor),f(\lfloor\frac{x+y}{2}\rfloor+1,y)) & \mathrm{otherwise} \\</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\end{cases}</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline"><</del>/<del class="diffchange diffchange-inline">math></del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">assuming that <math>x \le y<</del>/<del class="diffchange diffchange-inline">math></del>.<del class="diffchange diffchange-inline"><br</del>/<del class="diffchange diffchange-inline">></del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Hence, for example, the first query from the previous section would be <math>f(3,6)<</del>/<del class="diffchange diffchange-inline">math> and it would be recursively evaluated as <math>\min(f(3,4),f(5,6))<</del>/<del class="diffchange diffchange-inline">math></del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td></tr>
</table>
84.16.234.202
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=437&oldid=prev
Brian: Reverted edits by 119.252.144.111 (Talk) to last revision by Brian
2010-08-13T05:11:23Z
<p>Reverted edits by <a href="/wiki/Special:Contributions/119.252.144.111" title="Special:Contributions/119.252.144.111">119.252.144.111</a> (<a href="/wiki/index.php?title=User_talk:119.252.144.111&action=edit&redlink=1" class="new" title="User talk:119.252.144.111 (page does not exist)">Talk</a>) to last revision by <a href="/wiki/User:Brian" title="User:Brian">Brian</a></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 05:11, 13 August 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">bob</del>.<del class="diffchange diffchange-inline">schermerhorn evergreen commons</del>.<del class="diffchange diffchange-inline">com http:</del>//<del class="diffchange diffchange-inline">lanwilftasli</del>.<del class="diffchange diffchange-inline">xhost</del>.<del class="diffchange diffchange-inline">ro/david-b</del>.-<del class="diffchange diffchange-inline">eagan</del>.<del class="diffchange diffchange-inline">html www</del>.<del class="diffchange diffchange-inline">d.co.il 28867650  www.criss angle magic tricks.com http://lanwilftasli.xhost.ro/saddam.execution</del>-<del class="diffchange diffchange-inline">video.html whitehaven wines new zealand  dr.miracles http://lanwilftasli.xhost.ro/dentaire.com</del>-<del class="diffchange diffchange-inline">wanadoo.fr.html sharkey fr. cassidy genealogy  pickford film corp http://lanwilftasli.xhost.ro/balloon</del>-<del class="diffchange diffchange-inline">games.com.html 89.146.131.253 location  depositary nominees inc http://lanwilftasli.xhost.ro/missouri</del>-<del class="diffchange diffchange-inline">case.net.html coldcasefiles.com  pre teen models.com http</del>:<del class="diffchange diffchange-inline">//lanwilftasli</del>.<del class="diffchange diffchange-inline">xhost</del>.<del class="diffchange diffchange-inline">ro/www.pennsylvania</del>-<del class="diffchange diffchange-inline">arms</del>.<del class="diffchange diffchange-inline">html st. john s lutheran adrian  bates.com http:</del>//<del class="diffchange diffchange-inline">lanwilftasli.xhost.ro</del>/<del class="diffchange diffchange-inline">primetime.com.html o.j. simpson case  org.apache.commons.stringutils http</del>:<del class="diffchange diffchange-inline">//lanwilftasli.xhost.ro/dallergy-jr.html jaime johnson film maker  srlh3.0.exe http</del>://<del class="diffchange diffchange-inline">lanwilftasli</del>.<del class="diffchange diffchange-inline">xhost.ro</del>/<del class="diffchange diffchange-inline">www.charmed.net.html www.villa lago.com  www.criss angel.com http:</del>//<del class="diffchange diffchange-inline">lanwilftasli</del>.<del class="diffchange diffchange-inline">xhost.ro/dr.miracles.html marjorie eagan 96.9 fm</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">==Motivation==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">One of the most common applications of the segment tree is the solution to the [[range minimum query]] problem</ins>. <ins class="diffchange diffchange-inline">In this problem, we are given some array and repeatedly asked to find the minimum value within some specified range of indices</ins>. <ins class="diffchange diffchange-inline">For example, if we are given the array <math>[9,2,6,3,1,5,0,7]<</ins>/<ins class="diffchange diffchange-inline">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<</ins>/<ins class="diffchange diffchange-inline">math></ins>. <ins class="diffchange diffchange-inline">Then, another query might ask for the minimum element between the first and third, inclusive, and we would answer 2, and so on</ins>. <ins class="diffchange diffchange-inline">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</ins>. <ins class="diffchange diffchange-inline">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</ins>-<ins class="diffchange diffchange-inline">stating each time that we are doing so</ins>. <ins class="diffchange diffchange-inline">Bear in mind, however, that other types of segment tree exist, which are discussed later in the article</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">===The divide</ins>-<ins class="diffchange diffchange-inline">and</ins>-<ins class="diffchange diffchange-inline">conquer solution===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">The divide</ins>-<ins class="diffchange diffchange-inline">and</ins>-<ins class="diffchange diffchange-inline">conquer solution would be as follows</ins>:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* If the range contains one element, that element itself is trivially the minimum within that range</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* Otherwise, divide the range into two smaller ranges, each approximately half the size of the original, and find their respective minima</ins>. <ins class="diffchange diffchange-inline">The minimum for the original range is then the smaller of the two minima of the sub</ins>-<ins class="diffchange diffchange-inline">ranges</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Hence, if <math>a_i<</ins>/<ins class="diffchange diffchange-inline">math> denotes the <math>i<</ins>/<ins class="diffchange diffchange-inline">math><sup>th<</ins>/<ins class="diffchange diffchange-inline">sup> element in the array, finding the minimum could be encoded as the following recursive function</ins>:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<ins class="diffchange diffchange-inline"><math>\displaystyle</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">f(x,y) =</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\begin{cases}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">a_x & \mathrm{if\ } x = y \\</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\min(f(x,\lfloor\frac{x+y}{2}\rfloor),f(\lfloor\frac{x+y}{2}\rfloor+1,y)) & \mathrm{otherwise} \\</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\end{cases}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><</ins>/<ins class="diffchange diffchange-inline">math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">assuming that <math>x \le y<</ins>/<ins class="diffchange diffchange-inline">math></ins>.<ins class="diffchange diffchange-inline"><br</ins>/<ins class="diffchange diffchange-inline">></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Hence, for example, the first query from the previous section would be <math>f(3,6)<</ins>/<ins class="diffchange diffchange-inline">math> and it would be recursively evaluated as <math>\min(f(3,4),f(5,6))<</ins>/<ins class="diffchange diffchange-inline">math></ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td></tr>
</table>
Brian
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=369&oldid=prev
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
<p>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</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 23:45, 20 July 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">==Motivation==</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">bob</ins>.<ins class="diffchange diffchange-inline">schermerhorn evergreen commons</ins>.<ins class="diffchange diffchange-inline">com http:</ins>//<ins class="diffchange diffchange-inline">lanwilftasli</ins>.<ins class="diffchange diffchange-inline">xhost</ins>.<ins class="diffchange diffchange-inline">ro/david-b</ins>.-<ins class="diffchange diffchange-inline">eagan</ins>.<ins class="diffchange diffchange-inline">html www</ins>.<ins class="diffchange diffchange-inline">d.co.il 28867650  www.criss angle magic tricks.com http://lanwilftasli.xhost.ro/saddam.execution</ins>-<ins class="diffchange diffchange-inline">video.html whitehaven wines new zealand  dr.miracles http://lanwilftasli.xhost.ro/dentaire.com</ins>-<ins class="diffchange diffchange-inline">wanadoo.fr.html sharkey fr. cassidy genealogy  pickford film corp http://lanwilftasli.xhost.ro/balloon</ins>-<ins class="diffchange diffchange-inline">games.com.html 89.146.131.253 location  depositary nominees inc http://lanwilftasli.xhost.ro/missouri</ins>-<ins class="diffchange diffchange-inline">case.net.html coldcasefiles.com  pre teen models.com http</ins>:<ins class="diffchange diffchange-inline">//lanwilftasli</ins>.<ins class="diffchange diffchange-inline">xhost</ins>.<ins class="diffchange diffchange-inline">ro/www.pennsylvania</ins>-<ins class="diffchange diffchange-inline">arms</ins>.<ins class="diffchange diffchange-inline">html st. john s lutheran adrian  bates.com http:</ins>//<ins class="diffchange diffchange-inline">lanwilftasli.xhost.ro</ins>/<ins class="diffchange diffchange-inline">primetime.com.html o.j. simpson case  org.apache.commons.stringutils http</ins>:<ins class="diffchange diffchange-inline">//lanwilftasli.xhost.ro/dallergy-jr.html jaime johnson film maker  srlh3.0.exe http</ins>://<ins class="diffchange diffchange-inline">lanwilftasli</ins>.<ins class="diffchange diffchange-inline">xhost.ro</ins>/<ins class="diffchange diffchange-inline">www.charmed.net.html www.villa lago.com  www.criss angel.com http:</ins>//<ins class="diffchange diffchange-inline">lanwilftasli</ins>.<ins class="diffchange diffchange-inline">xhost.ro/dr.miracles.html marjorie eagan 96.9 fm</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">One of the most common applications of the segment tree is the solution to the [[range minimum query]] problem</del>. <del class="diffchange diffchange-inline">In this problem, we are given some array and repeatedly asked to find the minimum value within some specified range of indices</del>. <del class="diffchange diffchange-inline">For example, if we are given the array <math>[9,2,6,3,1,5,0,7]<</del>/<del class="diffchange diffchange-inline">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<</del>/<del class="diffchange diffchange-inline">math></del>. <del class="diffchange diffchange-inline">Then, another query might ask for the minimum element between the first and third, inclusive, and we would answer 2, and so on</del>. <del class="diffchange diffchange-inline">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</del>. <del class="diffchange diffchange-inline">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</del>-<del class="diffchange diffchange-inline">stating each time that we are doing so</del>. <del class="diffchange diffchange-inline">Bear in mind, however, that other types of segment tree exist, which are discussed later in the article</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">===The divide</del>-<del class="diffchange diffchange-inline">and</del>-<del class="diffchange diffchange-inline">conquer solution===</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">The divide</del>-<del class="diffchange diffchange-inline">and</del>-<del class="diffchange diffchange-inline">conquer solution would be as follows</del>:</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* If the range contains one element, that element itself is trivially the minimum within that range</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* Otherwise, divide the range into two smaller ranges, each approximately half the size of the original, and find their respective minima</del>. <del class="diffchange diffchange-inline">The minimum for the original range is then the smaller of the two minima of the sub</del>-<del class="diffchange diffchange-inline">ranges</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Hence, if <math>a_i<</del>/<del class="diffchange diffchange-inline">math> denotes the <math>i<</del>/<del class="diffchange diffchange-inline">math><sup>th<</del>/<del class="diffchange diffchange-inline">sup> element in the array, finding the minimum could be encoded as the following recursive function</del>:</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:<del class="diffchange diffchange-inline"><math>\displaystyle</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">f(x,y) =</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\begin{cases}</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">a_x & \mathrm{if\ } x = y \\</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\min(f(x,\lfloor\frac{x+y}{2}\rfloor),f(\lfloor\frac{x+y}{2}\rfloor+1,y)) & \mathrm{otherwise} \\</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">\end{cases}</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline"><</del>/<del class="diffchange diffchange-inline">math></del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">assuming that <math>x \le y<</del>/<del class="diffchange diffchange-inline">math></del>.<del class="diffchange diffchange-inline"><br</del>/<del class="diffchange diffchange-inline">></del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Hence, for example, the first query from the previous section would be <math>f(3,6)<</del>/<del class="diffchange diffchange-inline">math> and it would be recursively evaluated as <math>\min(f(3,4),f(5,6))<</del>/<del class="diffchange diffchange-inline">math></del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td></tr>
</table>
119.252.144.111
http://wcipeg.com/wiki/index.php?title=Segment_tree&diff=365&oldid=prev
Brian: Reverted edits by 193.254.155.110 (Talk) to last revision by Jargon
2010-07-11T14:55:42Z
<p>Reverted edits by <a href="/wiki/Special:Contributions/193.254.155.110" title="Special:Contributions/193.254.155.110">193.254.155.110</a> (<a href="/wiki/index.php?title=User_talk:193.254.155.110&action=edit&redlink=1" class="new" title="User talk:193.254.155.110 (page does not exist)">Talk</a>) to last revision by <a href="/wiki/index.php?title=User:Jargon&action=edit&redlink=1" class="new" title="User:Jargon (page does not exist)">Jargon</a></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 14:55, 11 July 2010</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">www</del>.<del class="diffchange diffchange-inline">g4 cheats</del>.<del class="diffchange diffchange-inline">com http:</del>//<del class="diffchange diffchange-inline">members</del>.<del class="diffchange diffchange-inline">multimania</del>.<del class="diffchange diffchange-inline">co.uk/mikustnecons/where-</del>is<del class="diffchange diffchange-inline">-jean-nv</del>.<del class="diffchange diffchange-inline">html www.bbbank.de  u.s. navy work shirt http://members.multimania.co.uk/mikustnecons/www.hrblock.comn.html www.computer share.com invester uk  www.asia.apple.com http://members.multimania.co.uk/mikustnecons/over</del>-<del class="diffchange diffchange-inline">stock</del>.<del class="diffchange diffchange-inline">com</del>.<del class="diffchange diffchange-inline">html duane.robidoux gmail.com  147.255 oklahoma http://members.multimania.co.uk/mikustnecons/www.andrewandcindy.com</del>-<del class="diffchange diffchange-inline">journal</del>-<del class="diffchange diffchange-inline">2006.html gloria model.com  about.reuters.com http</del>:<del class="diffchange diffchange-inline">//members</del>.<del class="diffchange diffchange-inline">multimania</del>.<del class="diffchange diffchange-inline">co</del>.<del class="diffchange diffchange-inline">uk</del>/<del class="diffchange diffchange-inline">mikustnecons</del>/<del class="diffchange diffchange-inline">www.reuters.co.in.html shotgunnews.comm  www.topnews.com http:</del>/<del class="diffchange diffchange-inline">/members.multimania.co.uk/mikustnecons/www.topnews.</del>in<del class="diffchange diffchange-inline">.html www.mountain madness.com  forest co.wisc snowmobile report http</del>:<del class="diffchange diffchange-inline">//members.multimania.co.uk/mikustnecons/healthnews-verizon.com.html myspace.com bballerchic923  dr. mack chemistry http</del>://<del class="diffchange diffchange-inline">members</del>.<del class="diffchange diffchange-inline">multimania.co.uk</del>/<del class="diffchange diffchange-inline">mikustnecons</del>/<del class="diffchange diffchange-inline">reuters.uk.html ct. unemployment  richard orth d.o http:</del>/<del class="diffchange diffchange-inline">/members</del>.<del class="diffchange diffchange-inline">multimania.co.uk/mikustnecons/wikileaks.com.html americas next top mode  thai embassy washington d c http://members.multimania.co.uk/mikustnecons/boise-city-fire-dept.html americas army 2.5 pc</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">==Motivation==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">One of the most common applications of the segment tree is the solution to the [[range minimum query]] problem</ins>. <ins class="diffchange diffchange-inline">In this problem, we are given some array and repeatedly asked to find the minimum value within some specified range of indices</ins>. <ins class="diffchange diffchange-inline">For example, if we are given the array <math>[9,2,6,3,1,5,0,7]<</ins>/<ins class="diffchange diffchange-inline">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<</ins>/<ins class="diffchange diffchange-inline">math></ins>. <ins class="diffchange diffchange-inline">Then, another query might ask for the minimum element between the first and third, inclusive, and we would answer 2, and so on</ins>. <ins class="diffchange diffchange-inline">Various solutions to this problem are discussed in the [[range minimum query]] article, but the segment tree </ins>is <ins class="diffchange diffchange-inline">often the most appropriate choice, especially when modification instructions are interspersed with the queries</ins>. <ins class="diffchange diffchange-inline">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</ins>-<ins class="diffchange diffchange-inline">stating each time that we are doing so</ins>. <ins class="diffchange diffchange-inline">Bear in mind, however, that other types of segment tree exist, which are discussed later in the article</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">===The divide-and-conquer solution===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">The divide</ins>-<ins class="diffchange diffchange-inline">and</ins>-<ins class="diffchange diffchange-inline">conquer solution would be as follows</ins>:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* If the range contains one element, that element itself is trivially the minimum within that range</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">* Otherwise, divide the range into two smaller ranges, each approximately half the size of the original, and find their respective minima</ins>. <ins class="diffchange diffchange-inline">The minimum for the original range is then the smaller of the two minima of the sub-ranges</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Hence, if <math>a_i<</ins>/<ins class="diffchange diffchange-inline">math> denotes the <math>i<</ins>/<ins class="diffchange diffchange-inline">math><sup>th<</ins>/<ins class="diffchange diffchange-inline">sup> element </ins>in <ins class="diffchange diffchange-inline">the array, finding the minimum could be encoded as the following recursive function</ins>:</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:<ins class="diffchange diffchange-inline"><math>\displaystyle</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">f(x,y) =</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\begin{cases}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">a_x & \mathrm{if\ } x = y \\</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\min(f(x,\lfloor\frac{x+y}{2}\rfloor),f(\lfloor\frac{x+y}{2}\rfloor+1,y)) & \mathrm{otherwise} \\</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\end{cases}</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><</ins>/<ins class="diffchange diffchange-inline">math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">assuming that <math>x \le y<</ins>/<ins class="diffchange diffchange-inline">math></ins>.<ins class="diffchange diffchange-inline"><br</ins>/<ins class="diffchange diffchange-inline">></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Hence, for example, the first query from the previous section would be <math>f(3,6)<</ins>/<ins class="diffchange diffchange-inline">math> and it would be recursively evaluated as <math>\min(f(3,4),f(5,6))<</ins>/<ins class="diffchange diffchange-inline">math></ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==Structure==</div></td></tr>
</table>
Brian