I have an AVL Tree which also calculate the index of each node (rank tree), I need to implement a function that gets minimum and maximum values and do the following:
Check how much elements of the tree falls inside this range (by the key of the nodes).
If the number of elements is a power of 2 it should update the elements key as so: (i =number of elements)
add 1 to the largest i/2 elements
add 1 to the largest i/4 elements
add 1 to the largest i/8 elements
...
add 1 to the largest element
- Returns the largest element in the range.
The complexity of this function should be O(log(i)*log(nodes_amount))
I was able to solve 1 and 3 base on the rank tree, I calculate how many nodes are less than maximum value and subtract the number of elements less than the minimum value, this cost O(log (nodes_amount)).
Returning the largest element in the range also possible in O(log (nodes_amount)) based on the AVL tree search.
The problem is with section 2 of the function which I can't figure out how to i-1 updates can be done in the required complexity.
It is possible that my approach isn't correct and BST isn't the solution for this problem.