552cfb37ea8cfa8aba0237e14cee5e81063d2d8d,rllib/optimizers/segment_tree.py,SegmentTree,reduce,#SegmentTree#Any#Any#,55

Before Change

            end = self._capacity - 1
        if end < 0:
            end += self._capacity
        return self._reduce_helper(start, end, 1, 0, self._capacity - 1)

    def __setitem__(self, idx, val):
        // index of the leaf
        idx += self._capacity

After Change

        // 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

    def __setitem__(self, idx, val):
        
        Inserts/overwrites a value in/into the tree.

Instances