class_docstr: A simple balanced binary order statistic tree to help compute the concordance.
  
  When computing the concordance, we know all the values the tree will ever contain. That
  condition simplifies this tree a lot. It means that instead of crazy AVL/red-black shenanigans
  we can simply do the following:
  
  - Store the final tree in flattened form in an array (so node i's children are 2i+1, 2i+2)
  - Additionally, store the current size of each subtree in another array with the same indices
  - To insert a value, just find its index, increment the size of the subtree at that index and
    propagate
  - To get the rank of an element, you add up a bunch of subtree counts
class_docstr_tok: ["A","simple","balanced","binary","order","statistic","tree","to","help","compute","the","concordance",".","When","computing","the","concordance",",","we","know","all","the","values","the","tree","will","ever","contain",".","That","condition","simplifies","this","tree","a","lot",".","It","means","that","instead","of","crazy","AVL\/red-black","shenanigans","we","can","simply","do","the","following",":","-","Store","the","final","tree","in","flattened","form","in","an","array","(","so","node","i","'s","children","are","2i+1",",","2i+2",")","-","Additionally",",","store","the","current","size","of","each","subtree","in","another","array","with","the","same","indices","-","To","insert","a","value",",","just","find","its","index",",","increment","the","size","of","the","subtree","at","that","index","and","propagate","-","To","get","the","rank","of","an","element",",","you","add","up","a","bunch","of","subtree","counts"]
docstr: Convert the np.ndarray `values` into a complete balanced tree.
  
  Assumes `values` is sorted ascending. Returns a list `t` of the same length in which t[i] >
  t[2i+1] and t[i] < t[2i+2] for all i.
docstr_tok: ["Convert","the","np.ndarray","`","values","`","into","a","complete","balanced","tree",".","Assumes","`","values","`","is","sorted","ascending",".","Returns","a","list","`","t","`","of","the","same","length","in","which","t","[","i","]",">","t","[","2i+1","]","and","t","[","i","]","<","t","[","2i+2","]","for","all","i","."]
code: def _treeify(values):
      """Convert the np.ndarray `values` into a complete balanced tree.
  
      Assumes `values` is sorted ascending. Returns a list `t` of the same length in which t[i] >
      t[2i+1] and t[i] < t[2i+2] for all i."""
      if len(values) == 1:  # this case causes problems later
          return values
      tree = np.empty_like(values)
      # Tree indices work as follows:
      # 0 is the root
      # 2n+1 is the left child of n
      # 2n+2 is the right child of n
      # So we now rearrange `values` into that format...
  
      # The first step is to remove the bottom row of leaves, which might not be exactly full
      last_full_row = int(np.log2(len(values) + 1) - 1)
      len_ragged_row = len(values) - (2 ** (last_full_row + 1) - 1)
      if len_ragged_row > 0:
          bottom_row_ix = np.s_[: 2 * len_ragged_row : 2]
          tree[-len_ragged_row:] = values[bottom_row_ix]
          values = np.delete(values, bottom_row_ix)
  
      # Now `values` is length 2**n - 1, so can be packed efficiently into a tree
      # Last row of nodes is indices 0, 2, ..., 2**n - 2
      # Second-last row is indices 1, 5, ..., 2**n - 3
      # nth-last row is indices (2**n - 1)::(2**(n+1))
      values_start = 0
      values_space = 2
      values_len = 2**last_full_row
      while values_start < len(values):
          tree[values_len - 1 : 2 * values_len - 1] = values[
              values_start::values_space
          ]
          values_start += int(values_space / 2)
          values_space *= 2
          values_len = int(values_len / 2)
      return tree
  
imports: import numpy
label_desc: Use image node_id 2 for calling the _BTree obj's underlying member method code with example usage: obj._treeify(values) and returns: tree, values