title: Segment tree implementation in Python
body: <p>I am solving <a href="http://www.spoj.com/problems/GSS1/" rel="nofollow noreferrer">this</a> problem using <a href="https://en.wikipedia.org/wiki/Segment_tree" rel="nofollow noreferrer">segment tree</a> but I get time limit error.
  Below is my raw code for range minimum query and by changing <code>min</code> to <code>max</code> in my code the above problem can be solved . I don't know how I can improve the performance of my code. Can you help me with its performance issues ?</p>
  
  <pre class="lang-py prettyprint-override"><code>t = [None] * 2 * 7      # n is length of list
  
  
  def build(a, v, start, end):
      '''
      A recursive function that constructs Segment Tree for list a.
      v is the starting node
      start and end are the index of array
      '''
  
      n = len(a)
      if start == end:
          t[v] = a[start]
      else:
          mid = (start + end) / 2
          build(a, v * 2, start, mid)     # v*2 is left child of parent v
          # v*2+1 is the right child of parent v
          build(a, v * 2 + 1, mid + 1, end)
          t[v] = min(t[2 * v], t[2 * v + 1])
      return t
  
  print build([18, 17, 13, 19, 15, 11, 20], 1, 0, 6)
  
  inf = 10**9 + 7
  
  
  def range_minimum_query(node, segx, segy, qx, qy):
      '''
      returns the minimum number in range(qx,qy)
      segx and segy represent the segment index
  
      '''
      if qx &gt; segy or qy &lt; segx:      # query out of range
          return inf
      elif segx &gt;= qx and segy &lt;= qy:  # query range inside segment range
          return t[node]
      else:
          return min(range_minimum_query(node * 2, segx, (segx + segy) / 2, qx, qy), range_minimum_query(node * 2 + 1, ((segx + segy) / 2) + 1, segy, qx, qy))
  
  print range_minimum_query(1, 1, 7, 1, 3)
  
  # returns 13
  </code></pre>
  
  <p>Can this be implemented iteratively ?</p>