Count inversions of size three using a segment tree

Updated

Given an array arr[] of size n. Three elements arr[i], arr[j] and arr[k] form an inversion of size 3 if a[i] > a[j] >a[k] and i < j < k. Find total number of inversions of size 3

Examples :

Input : {8, 4, 2, 1}
Output : 4
The four inversions are (8, 4, 2), (8, 4, 1), (4, 2, 1) and (8, 2, 1).

Input : {9, 6, 4, 5, 8}
Output : 2
The two inversions are {9, 6, 4} and {9, 6, 5}

The steps involved are:
1) Firstly data compression with help of map(STL container) or we can also do data compression by storing in another temp array and than replacing the original array with compressed values
2) then counting larger elements than a[i] having index smaller than i with help of ST
3) than counting smaller elements than a[i] having greater index than i with help of ST
We can reduces the complexity of this problem to O(n*log(n)) by Segment tree

The compressed array 3, 2, 1, 0 with the larger count on the left and the smaller count on the right of each middle element, giving 4 triples.

Segment Tree with point update & range query

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int smaller[100001]= {0}, larger[100001]= {0};
int dp[400001]= {0};
// std ST insertion operation 
// it will increase count of i into ST
void insert(int st, int ss, int se, int i)
{
    if(ss == se)
    {
        dp[st] ++;
        return ;
    }
    int mid = (ss + se) / 2;
    if (i<= mid)
        insert(2*st, ss, mid, i);
    else
        insert(2*st + 1, mid + 1, se, i);

    dp[st] = dp[2*st] + dp[2*st + 1];
}
// std ST query operation 
// return count of elements in range [i, j]
int query(int st, int ss, int se, int i, int j)
{
    if (se<ss || ss>j || se<i)
        return 0;
    if(ss>= i&&se<= j)
        return dp[st];
    int mid = (ss + se)/2;
    int xx = query(2*st, ss, mid, i, j)+query(2*st + 1, mid + 1, se, i, j);
    return xx;
}
int countInversion(int a[], int n)
{
    int i;
    // map is used for data compression 
    // by data compression we mean that if our input array is [8, 4, 2, 1] then we only have to compare values
    // i.e. a[i] > a[j] > a[k] for i < j < k. We don't have to care about what is difference between a[i] & a[j]
    // so by using map we convert [8, 4, 2, 1] into [3, 2, 1, 0].  
    // [3, 5, 2, 7, 3] --> [1, 2, 0, 3, 1]
    map<int, int> mp;
    for(i = 0; i<n; i++)
    {
        mp[a[i]]++;
    }
    map<int, int>::iterator it;
    i = 0;
    it = mp.begin();
    while(it != mp.end())
    {
        it->second = i;
        i ++;
        it ++;
    }
    for(i = 0 ; i < n ; i ++)
    {
        a[i]= mp[a[i]];
    }
    // larger[i] contains number of elements larger than a[i] and their index less than i
    for(i = 0; i<n; i++)
    {
        larger[i] = query(1, 0, n-1, a[i]+1, n);
        // in query we are calculating larger number than a[i] i.e. between a[i]+1 and n(n-1 is largest number
        // that we confirmed by map) and having index smaller than i
        // when i = x some intermediate step in for loop only 0 to x-1 index elements are inserted till now
        // so there is no case of larger value that any a[i] in segment tree(ST) having greater index than i 
        insert(1, 0, n-1, a[i]);
        // here we are inserting a[i] into ST 
    }
    for(i = 0; i<4*n; i++)
        dp[i]= 0;
    // smaller[i] contains number of elements smaller than a[i] and their index greater than i
    for(i = n-1; i>= 0; i--)
    {
        smaller[i] = query(1, 0, n, 0, a[i]-1);
         // in query we are calculating smaller number than a[i] i.e. between 0 and a[i]-1 as 0 is smallest 
         // number in array
        // when i = x some intermediate step in for loop only x + 1 to n-1 index elements are inserted till now
        // so there is no case of smaller value that any a[i] in segment tree(ST) having greater index than i
        insert(1, 0, n, a[i]);
        // here we are inserting a[i] into ST
    }
    ll ans = 0;
    for(i = 0; i<n; i++)
    {
        // for an index i larger[i] contains count of number having value greater than a[i] & index less than i
        // for an index i smaller[i] contains count of number having value smaller than a[i] & index greater than i
        // so if i index element is middle element than larger[i]*smaller[i] number of ways possible with i as 
        // middle element in inversion 
        ans += larger[i]*smaller[i];
    }
    return ans;
}
int main()
{
    int a[] = {8, 4, 2, 1};
    int n = sizeof(a)/sizeof(a[0]);
    cout << "Inversion Count : " << countInversion(a, n);
    return 0;
}

Output :

Inversion Count : 4

Time Complexity : O(n*log(n))
Space Complexity : O(n)

Comment
Mithlesh Upadhyay Published 19 Nov 2026 · 5 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials