class_docstr: Fast weighted sampling.
  
  list-like data structure
  append, update are O(log n)
  summation over an interval is O(log n) per query
class_docstr_tok: ["Fast","weighted","sampling",".","list-like","data","structure","append",",","update","are","O","(","log","n",")","summation","over","an","interval","is","O","(","log","n",")","per","query"]
code: def _allocindex(self, ix):
      if self.bd is None:
          self.bd = (ix, ix + 1)
      while ix >= self.bd[1]:
          r_bd = (self.bd[1], self.bd[1] * 2 - self.bd[0])
          left = SumTree(self.bd, self.left, self.right, self.s)
  
          right = SumTree(bd=r_bd)._initdescendant()
          self.bd = (left.bd[0], right.bd[1])
          self.left = left
          self.right = right
          # no need to update self.s because self.right.s == 0
      while ix < self.bd[0]:
          l_bd = (self.bd[0] * 2 - self.bd[1], self.bd[0])
          left = SumTree(bd=l_bd)._initdescendant()
          right = SumTree(self.bd, self.left, self.right, self.s)
          self.bd = (left.bd[0], right.bd[1])
          self.left = left
          self.right = right
  
imports: import collections
  import numpy
  from chainerrl.misc.random import sample_n_k
label_desc: Use image node_id 7 for calling the SumTree obj's underlying member method code with example usage: obj._allocindex(ix) without return types