I need help with this problem, I have given array of N elements, and I want to generate new array in which for every index I will be keeping how many numbers are on left of this index and are bigger than this element.
Let's say we have this array {3,2,1,0} and i want to generate this array {0, 1,2,3}. In the second array we have zero because there are no elements on left of the element 3, we have 1 because number 3 is on the left of number 2 and it is bigger...
I think this could be done with binary index tree, but i don't know how to implement it.
Thanks in advance.
You can do this in NlogN by constructing a binary tree and saving some metadata on the nodes along the way - namely the current size of the right subtree of each node. After each element is added, you can count the number of elements that were previously added to the tree that are larger than it. I will assume you know how to create a binary search tree by inserting nodes one by one. So let's split this into two things we need to do:
Maintain the size of the right subtree of each node: At each node we pick if the current value goes on the right subtree (current value is larger than the node value) or left subtree. If we choose to go right, increment the value of the rightSubtreeSize by one.
Count how many elements that were previously inserted are larger than the current element: Assuming that for each node we know the size of the right subtree, we can now count how many elements to the left of the current element are larger than it (i.e. elements to the left have already been added to the tree). Again, we follow the binary tree insert operation. At each node, if the current value is smaller than the node, it means that the node and it's whole right subtree are larger than the current value. so for each node we traverse, we keep a sum of all the elements that are larger than the current value. By the time we finish inserting to the tree, we have the sum we are looking for.
Let me know if you need any clarification.