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 librarytypedef 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.