Returns the number of occurrences of num in interval [0, index] in the list >>> root = build_tree(test_array) >>> rank_till_index(root, 6, 6) 1 >>> rank_till_index(root, 2, 0) 1 >>> rank_till_index(root, 1, 10) 2 >>> rank_till_index(root, 17, 7) 0 >>> ra
(node: Node | None, num: int, index: int)
| 68 | |
| 69 | |
| 70 | def rank_till_index(node: Node | None, num: int, index: int) -> int: |
| 71 | """ |
| 72 | Returns the number of occurrences of num in interval [0, index] in the list |
| 73 | |
| 74 | >>> root = build_tree(test_array) |
| 75 | >>> rank_till_index(root, 6, 6) |
| 76 | 1 |
| 77 | >>> rank_till_index(root, 2, 0) |
| 78 | 1 |
| 79 | >>> rank_till_index(root, 1, 10) |
| 80 | 2 |
| 81 | >>> rank_till_index(root, 17, 7) |
| 82 | 0 |
| 83 | >>> rank_till_index(root, 0, 9) |
| 84 | 1 |
| 85 | """ |
| 86 | if index < 0 or node is None: |
| 87 | return 0 |
| 88 | # Leaf node cases |
| 89 | if node.minn == node.maxx: |
| 90 | return index + 1 if node.minn == num else 0 |
| 91 | pivot = (node.minn + node.maxx) // 2 |
| 92 | if num <= pivot: |
| 93 | # go the left subtree and map index to the left subtree |
| 94 | return rank_till_index(node.left, num, node.map_left[index] - 1) |
| 95 | else: |
| 96 | # go to the right subtree and map index to the right subtree |
| 97 | return rank_till_index(node.right, num, index - node.map_left[index]) |
| 98 | |
| 99 | |
| 100 | def rank(node: Node | None, num: int, start: int, end: int) -> int: |