Count smaller elements on right side and greater elements on left side using Binary Index Tree

Approach

Brute-force: 

A simple solution is to iterate over the whole array for each element and count elements that are smaller on the right and greater on the left. We will need to use the nested loops. So the time complexity of this approach is O(N ²) which is very slow in terms of time complexity.

Efficient: 

We can solve this problem efficiently by using Binary Indexed Tree or Fenwick Tree. The main idea is to use array elements as indexes of the Binary Indexed Tree. So whether an element exists or not in Binary Indexed Tree can be checked in logarithmic time. 

Note: Input array has been transformed from integers to [1, n] while retaining their relative order. For example {-5, 10, 2, 5} is transformed to {1, 4, 2, 3}

To count smaller elements on the right:

i) Initialize a BIT of size n+1 with 0s. 

ii) Traverse the transformed array from right to left and do the following.

a) Count how many elements smaller than the current element are present in the BIT[ ]. This can be calculated using the Sum() function of the Binary Indexed Tree, which runs in logarithmic time (all elements on the right would have already been updated in the tree).

b) Now add the current element to BIT[ ] by performing an update operation that increments the count of the current element by one and therefore increments the count of ancestors of the current element.

Example dry run:

Here we will iterate from i = 4 to i = 0: (Keep in mind that we are using array element as indexes in BIT[ ])

i=4

Ans[4] = sum(A[4]-1)  // sum function will return 0 as we initialized BIT[ ] with 0s.

Now we call Update(A[4], 1) this will increase the count of all elements of BIT[ ] whose range includes ‘1’.

i=3

Ans[3] = sum(A[3]-1)  // sum function will return 1 because we incremented the count of ‘1’ in BIT[ ] by one.

Now we call Update(A[3], 1) this will increase the count of all elements of BIT[ ] whose range includes ‘2’.

i=2

Ans[2] = sum(A[2]-1)  // sum function will return 2 because we incremented the count of ‘1’ & ‘2’  in BIT[ ] by one (in previous updates).

Now we call Update(A[2], 1) this will increase the count of all elements of BIT[ ] whose range includes ‘3’.

And answer is calculated similarly for other elements in array A[ ].

To count greater elements on the left:

i) Reset BIT array. 

ii) Traverse the transformed array from left to right and do the following.

a) Count how many elements on the left, smaller than or equal to the current element are present in the BIT[ ]. This is calculated using Sum(). Since we have counted the number of smaller or equal elements to the current element. Count of elements on the left that are greater than the current element will be i-Sum().

b) Add the current element to BIT[ ] by performing an update operation that increments the count of the current element by 1.

Algorithm

1. Transform the input array integers into [1, n] while preserving the relative order of the elements. For example {-5, 10, 2, 5} is transformed to {1, 4, 2, 3}.

2. Traverse the transformed array from right to left and count the elements smaller than the current element using Binary Indexed Tree. 

3. Traverse the transformed array from left to right and count the elements smaller than or equal to the current element using Binary Indexed Tree. Then count of elements on the right that are greater than the current element will be i-sum().

4. Print the final answers.

Program

#include <bits/stdc++.h>
using namespace std;
 
#define mxSIZE 100000
#define pii pair<int, int>
#define S second
#define F first
 
 
/*--------------- BINARY INDEXED TREE. //BEGINS -----------*/
vector<int>BIT;
 
/**
 * @brief This is a utility function which calculate
 * the sum of array[0 ... idx] using BIT data structure.
 *
 * @param idx Index tree node.
 * @return int
 */
int Sum(int idx){
    int _sum = 0;
 
    /* Traversing the ancestors of idx node. */
    while(idx > 0){
        _sum += BIT[idx]; // Add current element in count.
 
        idx -= (idx & -idx); // Move to 'sum' parent node.
    }
    // Return count of smaller element on right side.
    return _sum;
}
 
/**
 * @brief This function updates a node of Binary Indexed Tree(BIT)
 * at given index 'idx'. Given value 'change' is added to BIT[idx] node
 * and its ancestors.
 *
 * @param idx Index tree node.
 * @param change Effective difference that needs to be updated.
 * @return void
 */
void Update(int idx, int change){
 
    /* Traverse over all ancestors of BIT[idx] and add 'change' */
    while(idx < BIT.size()){    
        BIT[idx] += change; // Add 'change' in current node.
 
        idx += (idx & -idx); // Move to 'update' parent node.
    }
}
/*--------------- BINARY INDEXED TREE. //ENDS   -----------*/
 
 
/**
 * @brief This function transforms an array into an array containing
 * elements from 1 to n(Preserving the relative order between the elements). For example {-4, 10, 5} --> {1, 3, 2}
 *
 * @param v Input array.
 */
void transformArray(vector<int> &v){
    int sz = v.size();
    vector<pii>temp(sz);
 
    for(int i=0; i<sz; i++)
        temp[i].F = v[i], temp[i].S = i;
   
    sort(temp.begin(), temp.end());
 
    for(int i=0; i<sz; i++){
        v[temp[i].S] = i+1;
    }
}
 
// Main function which gives arrays containing number of smaller elements on the right
// and greater elements on the left.
void solve(vector<int> &v, int n){
 
    // Converting array to an array containing elements from [1, n]
    transformArray(v);
    BIT.clear();
 
    /**
     * Create a Binary Indexed Tree of size equal to
     * maxElement + 1. ('+1' so that the elements can directly
     * be used as index)
     */
    BIT.resize(n+1, 0);
 
    // To store count of smaller elements on right
    // of greater elements on left.
    vector<int> cntSmallerRight(n), cntGreaterLeft(n);
 
    /* Calculate count of smaller elements on right */
    for(int i=n-1; i>=0; i--){
        // Get count of elements smaller than v[i].
        cntSmallerRight[i] = Sum(v[i]-1);
 
        // Update current element in the BIT
        Update(v[i], 1);
    }
 
    BIT.clear();
    BIT.resize(n+1, 0);
 
    /* Calculate count of greater elements on left */
    for(int i=0; i<n; i++){
        // Get count of elements greater than v[i].
        cntGreaterLeft[i] = i - Sum(v[i]-1);
       
        // Update current element in the BIT
        Update(v[i], 1);
    }
 
    cout << "Count of Smaller on right: ";
    for(int i=0; i<n; i++)cout << cntSmallerRight[i] << " ";
    cout<<endl;
 
    cout << "Count of Greater on left: ";
    for(int i=0; i<n; i++)cout << cntGreaterLeft[i] << " ";
    cout<<"\n\n";
}
 
// Driver Function.
int main(){
    int tt = 1;
    cin >> tt;
    while(tt--){
        int n; cin >> n;
        vector<int>v(n);
 
        for(int i=0; i<n; i++)cin >> v[i];
 
        solve(v, n);
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

INPUT

3
7
12 1 2 3 0 11 4
5
5 4 3 2 1
5
1 2 3 4 5

OUTPUT

Count of Smaller on right: 6 1 1 1 0 1 0
Count of Greater on left: 0 1 1 1 4 1 2
 
Count of Smaller on right: 4 3 2 1 0
Count of Greater on left: 0 1 2 3 4
 
Count of Smaller on right: 0 0 0 0 0
Count of Greater on left: 0 0 0 0 0

Time Complexity

The time complexity of the above approach is O(N * logN).

Space Complexity

The auxiliary space complexity of the program is O(N).

FAQs

1. What is Fenwick Tree or Binary Indexed Tree?
   A Fenwick tree or Binary Indexed Tree is a data structure that allows efficient calculations of prefix sums and efficient updates of elements in the array (while retaining tree structure & all its properties). 
    
2. What is the time complexity of insertion and query in a Fenwick Tree or Binary Indexed Tree?
   The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).
    
3. What is the advantage of Fenwick tree over Segment tree?
   The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.
    
4. What is the disadvantage of the Fenwick tree over the Segment tree?
   We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

Key Takeaways

Do check out a similar question here.

Check out this problem - Next Smaller Element

Cheers if you reached here!! 

This article discussed an intriguing problem using the Fenwick Tree or Binary Indexed Tree. Fenwick Tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!