code: def find_prefixsum_idx(self, prefixsum):
          
          assert 0 <= prefixsum <= self.sum() + 1e-5
          idx = 1
          while idx < self._capacity:  # while non-leaf
              if self._value[2 * idx] > prefixsum:
                  idx = 2 * idx
              else:
                  prefixsum -= self._value[2 * idx]
                  idx = 2 * idx + 1
          return idx - self._capacity
docs: Find the highest index `i` in the array such that
              sum(arr[0] + arr[1] + ... + arr[i - i]) <= prefixsum
  
          if array values are probabilities, this function
          allows to sample indexes according to the discrete
          probability efficiently.
  
          Parameters
          ----------
          perfixsum: float
              upperbound on the sum of array prefix
  
          Returns
          -------
          idx: int
              highest index satisfying the prefixsum constraint