How can we calculate, for every element in an array, the number of elements to the right that are greater than that element?

Quick summary of the problem statement: Given an array A which contains N integers, construct an array X such that for every i, X[i] = the number of elements in A that have an index greater than i and are also greater than A[i].

One way to solve this problem would be to use a binary search tree. Start by iterating from the last to the first element, adding each element to the set as we iterate. Every time we are at an element e, use the binary search tree's find() operation to find how many elements are greater than e in the current tree.

Perhaps your first thought would be to use a std::multiset (not std::set because we may have duplicate elements!), which is a self-balancing binary search tree that offers O(logN) insertion and O(logN) element finding. This seems like it would work for this algorithm, but it actually wouldn't. The reason is because when you call std::multiset::find(), it returns an iterator to the element in the set. Finding how many elements in the set are actually greater than the element would take O(N) time, as to find the distance from the iterator to the end of the set would require incrementing it repeatedly.

To solve this problem, we use an "indexed multiset", which is a slightly modified binary search tree such that we can find the index of an element in the multiset in O(logN) time while still supporting O(logN) insertion. Here's my code demonstrating this data structure:

#include <iostream>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

// I know this is kind of messy, but it's the general way to get a C++ indexed
// multiset without using an external library
typedef tree <int, null_type, less_equal <int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

int main()
{
    int A_size;
    cin >> A_size;

    vector <int> A(A_size);
    for(int i = 0; i < A_size; ++i){
        cin >> A[i];
    }
    // Input Done

    indexed_set nums;
    vector <int> X(A_size);
    for(int i = A_size - 1; i >= 0; --i){
        // order_of_key returns the first index that A[i] would be at in a sorted list
        // with the same elements as nums.
        X[i] = nums.size() - nums.order_of_key(A[i]);

        nums.insert(A[i]);
    }

    for(int item : X){
        cout << item << " ";
    }
    cout << "\n";

    return 0;
}

So, overall, the general strategy would be to

1. Iterate from the last element to the first element.
2. For every element, check in nums to see how many elements are greater than the current element. (O(logN))
3. Then, insert the current element and continue to iterate. (O(logN)) Clearly, the total time complexity of this algorithm is O(NlogN) and the space complexity is O(N).

A quick summary of the observations and insights of this method:

1. INSIGHT: If we iterate from the last to the first element (not the first to the last), the indexed-set will only contain elements to the right of the current element at any given iteration, which is exactly what we want. This saves us time because we don't need to worry about inserting all the elements at the beginning then removing them one by one if we were to iterate from left to right.

2. OBSERVATION: A std::set wouldn't suffice for the binary search tree in this algorithm because although it provides O(logN) finding an element, calculating the elements position in the set requires a worst case of O(N) time. An indexed-set, however, provides this "position-finding" operation in O(logN) time, as well as insertion.

Telescope has first mentioned (in the comments) that you can use a Binary tree to achieve that. However, you can do it also with the following alternative approach:

1. Use an AVL tree;
2. Each node should store the element and the number of elements on its right sub-tree;
3. Iterate the array from the end to the beginning;
4. Add to the tree and update the size on the nodes accordingly.
5. While adding compare the current element against the root; If this element is smaller than the root then it is smaller than all the elements to the right sub-tree. In this case, take the size from that node, and proceed to the left sub-tree and apply the same logic. Add the final size to the corresponded position on the array X;
6. If it is not smaller than the root then increase the size of the root and proceed to the appropriated sub-tree. And apply the aforementioned logic.

The time complexity will be N times inserting into the tree. Hence, O(n log(n)). And the space complexity will be naturally O(N).

Visualization :

A : [10,12,8,17,3,24,19];
X(A) [? ,? ,? ,? ,? ,? ,?]
Right Tree Node Size : S [?,?,?,?,?,?,?]

Inserting 19:

No elements in the right sub-tree therefore:

• size of 19 = 0;
• X(A) [? ,? ,? ,? ,? ,? ,0]
  
• S [?, ?, ?, ?, ?, ?, 0]

Inserting 24:

• 24 is greater than root (i.e., 19) so let us increase the size of the root and proceed to the sub right tree.
• Size of 24 = 0
• X(A) [? ,? ,? ,? ,? ,0 ,0]
  
• S [?, ?, ?, ?, ?, 0, 1]

Inserting 3:

• 3 is smaller than the root (i.e., 19) and the size of the root is 1, therefore there are 2 elements bigger than 3 the root and its right sub-tree. Let us go to the left;
• Size of 3 = 0
• X(A) [? ,? ,? ,? ,2 ,0 ,0]
• S [? , ?, ?, ?, 0, 0, 1]

Inserting 17:

• 17 is smaller than the root (i.e., 19) and the size of the root is 1, therefore there are 2 elements bigger than 17 the root and its right sub-tree. Let us go to the left, 17 is bigger than the root (i.e., 3), let us increase the size of node 3 from 0 to 1, and go to the right sub-tree.
• Size of 17 = 0
• X(A) [? ,? ,? ,2 ,2 ,0 ,0]
• S [? ,? ,? ,0 ,1 ,0 ,1]

Inserting 8:

• 8 is smaller than the root (i.e., 19) and the size of the root is 1, therefore there are 2 elements bigger than 8 the root and its right sub-tree. Let us go to the left, 8 is bigger than the root (i.e., 3), let us increase the size of node 3 from 1 to 2, and go to the right sub-tree. 8 is also smaller than the root (i.e., 17) so 8 is smaller to three elements so far. Let us go to the left.
• Size of 8 = 0
• X(A) [? ,? ,3 ,2 ,2 ,0 ,0]
• S [? ,? ,0 ,0 ,2 ,0 ,1]

With the insertion of the node 8 a rotation is performed to balance the tree.

During the rotation the sizes are also updated, namely the size of node 8 changed from 0 to 1 and the size of node 3 from 2 to 0.: - S [? ,? ,1 ,0 ,0 ,0 ,1]

Inserting 12:

• 12 is smaller than the root (i.e., 19) and the size of the root is 1, therefore there are 2 elements bigger than 12 the root and its right sub-tree. Let us go to the left, 12 is bigger than the root (i.e., 8), let us increase the size of node 8 from 1 to 2, and go to the right sub-tree. 12 is also smaller than the root (i.e., 17) so 12 is smaller to three elements so far. Let us go to the left.

• Size of 12 = 0

• X(A) [? ,3 ,3 ,2 ,2 ,0 ,0]

• S [? ,0 ,0 ,0 ,2 ,0 ,1]

With the insertion of the node 12 a double rotation is performed to balance the tree.

During the rotation the sizes are also updated - S [? ,0 ,1 ,2 ,0 ,0 ,1]

Inserting 10:

• 10 is smaller than the root (i.e., 17) and the size of the root is 2, therefore there are 3 elements bigger than 10 the root and its right sub-tree. Let us go to the left, 10 is bigger than the root (i.e., 8), let us increase the size of node 8 from 1 to 2, and go to the right sub-tree. 10 is also smaller than the root (i.e., 12) so 10 is smaller to 4 elements so far. Let us go to the left.

• Size of 10 = 0
• X(A) [4 ,3 ,3 ,2 ,2 ,0 ,0]
• S [0 ,0 ,0 ,0 ,2 ,0 ,1]

A possible C implementation (the AVL code was adapted from source):

#include<stdio.h>
#include<stdlib.h>
 
struct Node{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
    int size;
};
 
int height(struct Node *N){
    return (N == NULL) ? 0 : N->height;
}

int sizeRightTree(struct Node *N){
    return (N == NULL || N -> right == NULL) ? 0 : N->right->height;
}
 
int max(int a, int b){
    return (a > b) ? a : b;
}
 
struct Node* newNode(int key){
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;
    node->size = 0;
    return(node);
}
 
struct Node *rightRotate(struct Node *y) {
    struct Node *x = y->left;
    struct Node *T2 = x->right;
 
    x->right = y;
    y->left = T2;
 
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
    y->size = sizeRightTree(y);
    x->size = sizeRightTree(x);
    return x;
}
 
struct Node *leftRotate(struct Node *x){
    struct Node *y = x->right;
    struct Node *T2 = y->left;
 
    y->left = x;
    x->right = T2;
 
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
    y->size = sizeRightTree(y);
    x->size = sizeRightTree(x); 

    return y;
}
 
int getBalance(struct Node *N){
    return (N == NULL) ? 0 : height(N->left) - height(N->right);
}
 
struct Node* insert(struct Node* node, int key, int *size){
    if (node == NULL)
        return(newNode(key));
    if (key < node->key){
        *size = *size + node->size + 1;
        node->left  = insert(node->left, key, size);
    } 
    else if (key > node->key){
    node->size++;
    node->right = insert(node->right, key, size);
    }
    else 
        return node;
 
    node->height = 1 + max(height(node->left), height(node->right));
    int balance = getBalance(node);
 
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);
    if (balance > 1 && key > node->left->key){
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    if (balance < -1 && key < node->right->key){
        node->right = rightRotate(node->right);
        return leftRotate(node);
    } 
    return node;
}

int main()
{
  int arraySize = 7;
  struct Node *root = NULL;
  int A[7] = {10,12,8,17,3,24,19};
  int X[7] ={0};
  for(int i = arraySize - 1; i >= 0; i--)
     root = insert(root, A[i], &X[i]);

  for(int i = 0; i < arraySize; i++)
     printf("%d ", X[i]);
  printf("\n");
  return 0;
}

OUTPUT:

4 3 3 2 2 0 0 

something similar to merge sort where counting in inserted after processing right and before processing left side of range, ex:

#include <algorithm>
#include <functional>

void count_greater_on_right( int* a, int* x, int begin, int end )
{
    if( end - begin <= 2 )
    {
        if( end - begin == 2 && a[begin] < a[begin+1] )
        {
            x[begin]+=1; // specific
            std::swap( a[begin], a[begin+1] );
        }
        return;
    }

    int middle =(begin+end+1)/2;
    count_greater_on_right( a, x, middle, end );

    // specific
    {
        for( int i=begin; i!=middle; ++i )
        {
            x[i]+=std::lower_bound( &a[middle], &a[end], a[i], std::greater<int>() )-&a[middle];
        }
    }

    count_greater_on_right( a, x, begin, middle );
    std::inplace_merge( &a[begin], &a[middle], &a[end], std::greater<int>() );
}

code, specific to the task, is commented with // specific; reverse order of sorting makes it slightly simpler IMHO; updates 'a' so if you need original sequence, create copy.

Problem can be solved if array is dived into sub ranges and then sort these sub ranges. Let's see in details,

Given array = [10, 12, 8, 17, 3, 24, 19]
Now divide array in sub range of length 4 and sort these sub ranges as showed below,
Sub rang sorted array

....................  ...............
| 8 | 10 | 12 | 17 |  | 3 | 19 | 24 |
....................  ...............
  2    0    1    3      4    6    5    => index

Let's take first entry of sub range sorted array which is 8 and try to find number of right elements greater then of 8
As you see in above number 8 belong to first sub range and because sub ranges are sorted, elements in sub range are in ascending order but not in there index order. It means in current sub range, we have to compare index of all elements at right of element 8 with index of element 8

Index of 8 is 2 but 10 have index = 0, it means 10 is at left of 8 in input array,
Index of 12 is also less then index of 8, it means 12 is at left of 8 in input array,
Index of 17 is 3 which is greater than index of 8, it means 17 is at the right of 8 in input array and can be considered greater element,
After comparing index of 8 with index of all right elements of current sub range, right greater element count = 1, let's look at the next range,

After sub range of 8, things got totally changed, now we know this sub range is at the right of the sub range element 8 belongs, it means we don't have to compare index of 8 with elements or this range, all are at right of element 8 and we only have to find how many are greater than 8,

Now we compare first element of right sub range with 8 and as you can see above first element is 3 which is less then 8 but in case if first element of right sub range is greater then current element then we can increment count directly to number of elements present in right sub range.

Because first element 3 is less then 8 we find upper bound of 8 in right sub range and that is 19 and all the elements from 19 in right sub range are greater than 8, so there are two elements 19, 24 and due to this count incremented by two and become count = 3
Finally there are 3 right elements greater than element 8.

In similar way number of greater right elements can be found for all elements and result array would be,
x(A) = [4, 3, 3, 2, 2, 0, 0]

Conclusion is, by dividing input array in sorted sub range, greater elements at right can be found by following steps,

1. Compare index of all right elements of current sub range,
   
2. Compare first element of right sub range and if,
   i. first element is greater then current element than all element of right range are greater then current element,
   ii. first element is less than, then find upper bound of current element in right sub range, and elements from upper bound in right sub range are greater than current element.
3. Repeat step 2 for all right sub ranges.

#include <iostream>

#include <vector>
#include <iterator>
#include <algorithm>

using std::cout;

std::vector<std::pair<int, std::size_t>> arrayOfSortedSubRange(std::size_t subRangeSize,
                                                              const std::vector<int>& numArr){


    std::vector<std::pair<int, std::size_t>> res;
    res.reserve(numArr.size());

    for(std::size_t i = 0, numArrSize = numArr.size(); i < numArrSize; ++i){

        res.emplace_back(numArr[i], i);
    }

    for(std::vector<std::pair<int, std::size_t>>::iterator it = res.begin(), endIt = res.end(); endIt != it;){

        std::vector<std::pair<int, std::size_t>>::iterator rangeEndIt = it + std::min<std::ptrdiff_t>(endIt - it,
                                                                                                      subRangeSize);

        std::sort(it, rangeEndIt, [](const std::pair<int, std::size_t>& a, const std::pair<int, std::size_t>& b){
            return a.first < b.first;});
        it = rangeEndIt;
    }

    return res;
}

std::size_t rightGreterElmentCountOfNumber(int num, std::vector<std::pair<int, std::size_t>>::const_iterator rightSubRangeIt,
                              std::vector<std::pair<int, std::size_t>>::const_iterator endIt){

    std::size_t count = 0;

    std::vector<std::pair<int, std::size_t>>::const_iterator subRangEndIt = rightSubRangeIt +
            std::min<std::ptrdiff_t>(endIt - rightSubRangeIt, 4);

    while(endIt != rightSubRangeIt){

        if(rightSubRangeIt->first > num){

            count += subRangEndIt - rightSubRangeIt;
        }
        else{
            count += subRangEndIt -
                    std::upper_bound(rightSubRangeIt, subRangEndIt, num, [](int num,
                                     const std::pair<int, std::size_t>& element){ return num < element.first;});
        }

        rightSubRangeIt = subRangEndIt;
        subRangEndIt += std::min<std::ptrdiff_t>(endIt - subRangEndIt, 4);
    }

    return count;
}

std::vector<std::size_t> rightGreaterElementCountForLessThanFiveNumbers(const std::vector<int>& numArr){

    std::vector<std::size_t> res(numArr.size(), 0);
    std::vector<std::size_t>::iterator resIt = res.begin();

    for(std::vector<int>::const_iterator it = numArr.cbegin(), lastIt = it + (numArr.size() - 1); lastIt != it;
        ++it, ++resIt){

        *resIt = std::count_if(it + 1, numArr.cend(), [num = *it](int rightNum){return rightNum > num;});
    }

    return res;
}

std::vector<std::size_t> rightGreaterElementCount(const std::vector<int>& numArr){

    if(numArr.size() < 5){

        return rightGreaterElementCountForLessThanFiveNumbers(numArr);
    }

    std::vector<std::size_t> resArr(numArr.size(), 0);
    std::vector<std::pair<int, std::size_t>> subRangeSortedArr = arrayOfSortedSubRange(4, numArr);

    for(std::vector<std::pair<int, std::size_t>>::const_iterator it = subRangeSortedArr.cbegin(),
        endIt = subRangeSortedArr.cend(); endIt != it;){

        std::vector<std::pair<int, std::size_t>>::const_iterator rightNextSubRangeIt = it + std::min<std::ptrdiff_t>(
                    endIt - it, 4);

        for(std::vector<std::pair<int, std::size_t>>::const_iterator eleIt = it; rightNextSubRangeIt != eleIt; ++eleIt){

            std::size_t count = std::count_if(eleIt, rightNextSubRangeIt, [index = eleIt->second](
                                              const std::pair<int, std::size_t>& element){ return index < element.second;});

            if(endIt != rightNextSubRangeIt){

                count += rightGreterElmentCountOfNumber(eleIt->first, rightNextSubRangeIt, endIt);
            }

            resArr[eleIt->second] = count;
        }

        it += std::min<std::ptrdiff_t>(endIt - it, 4);
    }

    return resArr;
}

int main(){

    std::vector<std::size_t> res = rightGreaterElementCount({10, 12, 8, 17, 3, 24, 19});

    cout<< "[10, 12, 8, 17, 3, 24, 19] => [";

    std::copy(res.cbegin(), res.cbegin() + (res.size() - 1), std::ostream_iterator<std::size_t>(cout, ", "));

    cout<< res.back()<< "]\n";
}

Output:
[10, 12, 8, 17, 3, 24, 19] => [4, 3, 3, 2, 2, 0, 0]