nodes: 0, module; 1, function_definition; 2, function_name:_build_index; 3, parameters; 4, block; 5, identifier:self; 6, expression_statement; 7, expression_statement; 8, if_statement; 9, expression_statement; 10, expression_statement; 11, expression_statement; 12, if_statement; 13, if_statement; 14, expression_statement; 15, expression_statement; 16, expression_statement; 17, while_statement; 18, expression_statement; 19, expression_statement; 20, comment:"""Build an index for indexing the sorted list.
  
          Indexes are represented as binary trees in a dense array notation
          similar to a binary heap.
  
          For example, given a _lists representation storing integers:
  
          [0]: 1 2 3
          [1]: 4 5
          [2]: 6 7 8 9
          [3]: 10 11 12 13 14
  
          The first transformation maps the sub-lists by their length. The
          first row of the index is the length of the sub-lists.
  
          [0]: 3 2 4 5
  
          Each row after that is the sum of consecutive pairs of the previous row:
  
          [1]: 5 9
          [2]: 14
  
          Finally, the index is built by concatenating these lists together:
  
          _index = 14 5 9 3 2 4 5
  
          An offset storing the start of the first row is also stored:
  
          _offset = 3
  
          When built, the index can be used for efficient indexing into the list.
          See the comment and notes on self._pos for details.
          """; 21, assignment; 22, comparison_operator:len(row0) == 1; 23, block; 24, assignment; 25, assignment; 26, assignment; 27, binary_operator:len(row0) & 1; 28, block; 29, comparison_operator:len(row1) == 1; 30, block; 31, assignment; 32, call; 33, assignment; 34, comparison_operator:len(tree[-1]) > 1; 35, block; 36, call; 37, assignment; 38, identifier:row0; 39, call; 40, call; 41, integer:1; 42, expression_statement; 43, expression_statement; 44, return_statement; 45, identifier:head; 46, call; 47, identifier:tail; 48, call; 49, identifier:row1; 50, call; 51, call; 52, integer:1; 53, expression_statement; 54, call; 55, integer:1; 56, expression_statement; 57, expression_statement; 58, return_statement; 59, identifier:size; 60, binary_operator:2 ** (int(log_e(len(row1) - 1, 2)) + 1); 61, attribute; 62, argument_list; 63, identifier:tree; 64, list; 65, call; 66, integer:1; 67, expression_statement; 68, expression_statement; 69, expression_statement; 70, expression_statement; 71, identifier:reduce; 72, argument_list; 73, attribute; 74, binary_operator:size * 2 - 1; 75, identifier:list; 76, argument_list; 77, identifier:len; 78, argument_list; 79, assignment; 80, assignment; 81, identifier:iter; 82, argument_list; 83, identifier:iter; 84, argument_list; 85, identifier:list; 86, argument_list; 87, identifier:len; 88, argument_list; 89, call; 90, identifier:len; 91, argument_list; 92, assignment; 93, assignment; 94, integer:2; 95, parenthesized_expression; 96, identifier:row1; 97, identifier:extend; 98, call; 99, identifier:row0; 100, identifier:row1; 101, identifier:len; 102, argument_list; 103, assignment; 104, assignment; 105, assignment; 106, call; 107, identifier:iadd; 108, call; 109, attribute; 110, identifier:self; 111, identifier:_offset; 112, binary_operator:size * 2; 113, integer:1; 114, call; 115, identifier:row0; 116, subscript; 117, identifier:row0; 118, attribute; 119, integer:0; 120, identifier:row0; 121, identifier:head; 122, call; 123, identifier:row0; 124, attribute; 125, argument_list; 126, identifier:row1; 127, subscript; 128, binary_operator:row1 + row0; 129, attribute; 130, integer:1; 131, binary_operator:int(log_e(len(row1) - 1, 2)) + 1; 132, identifier:repeat; 133, argument_list; 134, subscript; 135, identifier:head; 136, call; 137, identifier:tail; 138, call; 139, identifier:row; 140, call; 141, attribute; 142, argument_list; 143, identifier:reversed; 144, argument_list; 145, identifier:self; 146, identifier:_index; 147, identifier:size; 148, integer:2; 149, identifier:map; 150, argument_list; 151, attribute; 152, slice; 153, identifier:self; 154, identifier:_offset; 155, identifier:starmap; 156, argument_list; 157, identifier:row1; 158, identifier:append; 159, subscript; 160, attribute; 161, slice; 162, identifier:row1; 163, identifier:row0; 164, identifier:self; 165, identifier:_offset; 166, call; 167, integer:1; 168, integer:0; 169, binary_operator:size - len(row1); 170, identifier:tree; 171, unary_operator; 172, identifier:iter; 173, argument_list; 174, identifier:iter; 175, argument_list; 176, identifier:list; 177, argument_list; 178, identifier:tree; 179, identifier:append; 180, identifier:row; 181, identifier:tree; 182, identifier:len; 183, attribute; 184, identifier:self; 185, identifier:_index; 186, identifier:add; 187, call; 188, identifier:row0; 189, unary_operator; 190, identifier:self; 191, identifier:_index; 192, identifier:int; 193, argument_list; 194, identifier:size; 195, call; 196, integer:1; 197, subscript; 198, identifier:head; 199, call; 200, identifier:self; 201, identifier:_lists; 202, identifier:zip; 203, argument_list; 204, integer:1; 205, call; 206, identifier:len; 207, argument_list; 208, identifier:tree; 209, unary_operator; 210, identifier:starmap; 211, argument_list; 212, identifier:head; 213, identifier:tail; 214, identifier:log_e; 215, argument_list; 216, identifier:row1; 217, integer:1; 218, identifier:add; 219, call; 220, binary_operator:len(row1) - 1; 221, integer:2; 222, identifier:zip; 223, argument_list; 224, call; 225, integer:1; 226, identifier:head; 227, identifier:tail; 228, identifier:len; 229, argument_list; 230, identifier:row1
code: def _build_index(self):
          """Build an index for indexing the sorted list.
  
          Indexes are represented as binary trees in a dense array notation
          similar to a binary heap.
  
          For example, given a _lists representation storing integers:
  
          [0]: 1 2 3
          [1]: 4 5
          [2]: 6 7 8 9
          [3]: 10 11 12 13 14
  
          The first transformation maps the sub-lists by their length. The
          first row of the index is the length of the sub-lists.
  
          [0]: 3 2 4 5
  
          Each row after that is the sum of consecutive pairs of the previous row:
  
          [1]: 5 9
          [2]: 14
  
          Finally, the index is built by concatenating these lists together:
  
          _index = 14 5 9 3 2 4 5
  
          An offset storing the start of the first row is also stored:
  
          _offset = 3
  
          When built, the index can be used for efficient indexing into the list.
          See the comment and notes on self._pos for details.
          """
          row0 = list(map(len, self._lists))
  
          if len(row0) == 1:
              self._index[:] = row0
              self._offset = 0
              return
  
          head = iter(row0)
          tail = iter(head)
          row1 = list(starmap(add, zip(head, tail)))
  
          if len(row0) & 1:
              row1.append(row0[-1])
  
          if len(row1) == 1:
              self._index[:] = row1 + row0
              self._offset = 1
              return
  
          size = 2 ** (int(log_e(len(row1) - 1, 2)) + 1)
          row1.extend(repeat(0, size - len(row1)))
          tree = [row0, row1]
  
          while len(tree[-1]) > 1:
              head = iter(tree[-1])
              tail = iter(head)
              row = list(starmap(add, zip(head, tail)))
              tree.append(row)
  
          reduce(iadd, reversed(tree), self._index)
          self._offset = size * 2 - 1