class_docstr: A Segment Tree data structure.
  
  https://en.wikipedia.org/wiki/Segment_tree
  
  Can be used as regular array, but with two important differences:
  
    a) Setting an item's value is slightly slower. It is O(lg capacity),
       instead of O(1).
    b) Offers efficient `reduce` operation which reduces the tree's values
       over some specified contiguous subsequence of items in the array.
       Operation could be e.g. min/max/sum.
  
  The data is stored in a list, where the length is 2 * capacity.
  The second half of the list stores the actual values for each index, so if
  capacity=8, values are stored at indices 8 to 15. The first half of the
  array contains the reduced-values of the different (binary divided)
  segments, e.g. (capacity=4):
  0=not used
  1=reduced-value over all elements (array indices 4 to 7).
  2=reduced-value over array indices (4 and 5).
  3=reduced-value over array indices (6 and 7).
  4-7: values of the tree.
  NOTE that the values of the tree are accessed by indices starting at 0, so
  `tree[0]` accesses `internal_array[4]` in the above example.
class_docstr_tok: ["A","Segment","Tree","data","structure",".","https",":","\/\/en.wikipedia.org\/wiki\/Segment_tree","Can","be","used","as","regular","array",",","but","with","two","important","differences",":","a",")","Setting","an","item","'s","value","is","slightly","slower",".","It","is","O","(","lg","capacity",")",",","instead","of","O","(","1",")",".","b",")","Offers","efficient","`","reduce","`","operation","which","reduces","the","tree","'s","values","over","some","specified","contiguous","subsequence","of","items","in","the","array",".","Operation","could","be","e.g",".","min\/max\/sum",".","The","data","is","stored","in","a","list",",","where","the","length","is","2","*","capacity",".","The","second","half","of","the","list","stores","the","actual","values","for","each","index",",","so","if","capacity=8",",","values","are","stored","at","indices","8","to","15",".","The","first","half","of","the","array","contains","the","reduced-values","of","the","different","(","binary","divided",")","segments",",","e.g",".","(","capacity=4",")",":","0=not","used","1=reduced-value","over","all","elements","(","array","indices","4","to","7",")",".","2=reduced-value","over","array","indices","(","4","and","5",")",".","3=reduced-value","over","array","indices","(","6","and","7",")",".","4-7",":","values","of","the","tree",".","NOTE","that","the","values","of","the","tree","are","accessed","by","indices","starting","at","0",",","so","`","tree","[","0","]","`","accesses","`","internal_array","[","4","]","`","in","the","above","example","."]
docstr: Applies `self.operation` to subsequence of our values.
  
  Subsequence is contiguous, includes `start` and excludes `end`.
  
    self.operation(
        arr[start], operation(arr[start+1], operation(... arr[end])))
  
  Args:
      start: Start index to apply reduction to.
      end (Optional[int]): End index to apply reduction to (excluded).
  
  Returns:
      any: The result of reducing self.operation over the specified
          range of `self._value` elements.
docstr_tok: ["Applies","`","self.operation","`","to","subsequence","of","our","values",".","Subsequence","is","contiguous",",","includes","`","start","`","and","excludes","`","end","`",".","self.operation","(","arr","[","start","]",",","operation","(","arr","[","start+1","]",",","operation","(","...","arr","[","end","]",")",")",")","Args",":","start",":","Start","index","to","apply","reduction","to",".","end","(","Optional","[","int","]",")",":","End","index","to","apply","reduction","to","(","excluded",")",".","Returns",":","any",":","The","result","of","reducing","self.operation","over","the","specified","range","of","`","self._value","`","elements","."]
code: def reduce(self, start: int = 0, end: Optional[int] = None) -> Any:
      """Applies `self.operation` to subsequence of our values.
  
      Subsequence is contiguous, includes `start` and excludes `end`.
  
        self.operation(
            arr[start], operation(arr[start+1], operation(... arr[end])))
  
      Args:
          start: Start index to apply reduction to.
          end (Optional[int]): End index to apply reduction to (excluded).
  
      Returns:
          any: The result of reducing self.operation over the specified
              range of `self._value` elements.
      """
      if end is None:
          end = self.capacity
      elif end < 0:
          end += self.capacity
  
      # Init result with neutral element.
      result = self.neutral_element
      # Map start/end to our actual index space (second half of array).
      start += self.capacity
      end += self.capacity
  
      # Example:
      # internal-array (first half=sums, second half=actual values):
      # 0 1 2 3 | 4 5 6 7
      # - 6 1 5 | 1 0 2 3
  
      # tree.sum(0, 3) = 3
      # internally: start=4, end=7 -> sum values 1 0 2 = 3.
  
      # Iterate over tree starting in the actual-values (second half)
      # section.
      # 1) start=4 is even -> do nothing.
      # 2) end=7 is odd -> end-- -> end=6 -> add value to result: result=2
      # 3) int-divide start and end by 2: start=2, end=3
      # 4) start still smaller end -> iterate once more.
      # 5) start=2 is even -> do nothing.
      # 6) end=3 is odd -> end-- -> end=2 -> add value to result: result=1
      #    NOTE: This adds the sum of indices 4 and 5 to the result.
  
      # Iterate as long as start != end.
      while start < end:
          # If start is odd: Add its value to result and move start to
          # next even value.
          if start & 1:
              result = self.operation(result, self.value[start])
              start += 1
  
          # If end is odd: Move end to previous even value, then add its
          # value to result. NOTE: This takes care of excluding `end` in any
          # situation.
          if end & 1:
              end -= 1
              result = self.operation(result, self.value[end])
  
          # Divide both start and end by 2 to make them "jump" into the
          # next upper level reduce-index space.
          start //= 2
          end //= 2
  
          # Then repeat till start == end.
  
      return result
  
file_path: ray/rllib/execution/segment_tree.py
imports: import operator
  from typing import Any, Optional
label_desc: Use image node_id 2 for calling the SegmentTree obj's underlying member method code with example usage: obj.reduce(start, end) and returns: result