Number of elements greater than K in the range L to R using Fenwick Tree (Offline queries)

Algorithm:

1. Combine all the array elements and queries into a single data structure. We can implement our own structure or class for this purpose.
2. Sort the combined structure in descending order. If multiple elements have the same value, the query element will come first.
3. Create a Binary Indexed Tree such that query(i) will return the number of elements present in the array till index ‘i’. 
4. Iterate over the combined structure array. If the current element is an array element, increment the count of the index of that element.
5. If it is a query element, the number of elements greater than K between ‘L’ and ‘R’ will be equal to query(‘R’) - query(‘L’-1).
6. Print the answer.

C++ Code

#include <bits/stdc++.h>
using namespace std;

// Defining our own structure
typedef struct node {
    int val;
    int l;
    int r;
    int idx;
} Node;

// Writing our own comparator function
bool compare(Node a, Node b){

    // If both values are equal, query will come first
    if (a.val == b.val){
        return a.l > b.l;
    }

    // Otherwise, sort in descending order
    return a.val > b.val;
}

// Function to update the BIT
void update(int * BIT, int n, int idx){
    while (idx <= n){
        BIT[idx]++;
        idx += idx & (-idx);
    }
}

/*
This function will return the count of
elements present till index 'idx'.
*/
int query(int * BIT, int idx){
    int ans = 0;
    while (idx){
        ans += BIT[idx];
        idx -= idx & (-idx);
    }
    return ans;
}

// Driver code
int main(){
    int n = 7;
    int arr[] = { 5, 3, 6, 2, 4, 7, 6 };
    int q = 3;
    vector<int> queries[] = { {1, 4, 4}, {3, 7, 5}, {3, 7, 6} };

    // Creating structure for combining arr and queries
    Node a[n+q+1];

    // Iterating over array elements
    for(int i=1; i<=n; i++){
        a[i].val = arr[i-1];
        a[i].idx = i;
        a[i].l = -1;
        a[i].r = -1;
    }

    // Iterating over query elements
    for (int i=n+1; i<=n+q; i++){
        a[i].val = queries[i-n-1][2];
        a[i].l = queries[i-n-1][0];
        a[i].r = queries[i-n-1][1];
        a[i].idx = i-n;
    }

    // Sorting the structure using our comparator function
    sort(a+1, a+n+q+1, compare);

    // Creating Binary Indexed Tree
    int BIT[n+1];
    memset(BIT, 0, sizeof(BIT));
    int ans[q+1];

    // Iterating over the combined structure
    for (int i = 1; i <= n + q; ++i) {
      
        // Updating BIT if it is an array element
        if (a[i].l == -1){
            update(BIT, n, a[i].idx);
        }
        else{

            // Counting number of elements greater than K
            int curAns = query(BIT, a[i].r) - query(BIT, a[i].l - 1);
            ans[a[i].idx] = curAns;
        }
    }
  
    // Printing the answer array
    for (int i=1; i<=q; i++){
        cout << ans[i] << ' ';
    }
    cout<<endl;

    return 0;
}

Output

2 3 1

Algorithm Complexity

Time Complexity

We have implemented two functions for BIT:

update(): This function will increment the count for an array element in O(logN) time.

query(): This function returns the number of elements till index ‘i’ in O(logN) time.

For every array element, we are calling the update function. This will take O(NlogN) time, and for every query element, we are calling query function. This will take O(QlogN) time.

Total time complexity = O((N+Q)logN).

Space Complexity

We have created a structure to combine array and query elements. This will take O(N + Q) space. We have also implemented a BIT array of O(N+Q) length.

Total space complexity = O(N+Q).

FAQs

1. What is a Binary Indexed Tree?
   A Binary Indexed Tree or Fenwick tree is a data structure that can efficiently update elements and calculate prefix sums of a list of numbers. It allows both the operations to be performed in time complexity of O(logN).
    
2. What is the difference between BIT and Segment Tree?
   A segment tree can be used to do a range query on any range L and R, but BIT can only be used for prefix queries, i.e., L is always equal to 1. BIT is more efficient than Segment Tree as it has a comparatively small constant factor.
    
3. What is a structure in C/C++?
   Structures are user-defined data types in C/C++. They are used to group the items of different data types into a single data type. It is created using the ‘struct’ keyword.
    
4. What is an offline query?
   An offline query means that we can first store all the queries and then solve them in any order to calculate the answer more efficiently. This can be used only when the answer for one query is independent of the other.
    
5. Why do we decide to use offline queries in this problem?
   In this problem, we had to find the number of elements between L and R that are greater than K for multiple queries. Now if there was a single K, we can simply ignore the elements that are smaller than K and count the number of elements present between index L and R. But since K can vary from one query to another, we decided to process the queries in such a way that we can balance its effect. We decided to sort the queries in descending order of K so that we can store only the elements greater than the current K. Therefore, we decided to use offline queries approach.

Key Takeaways

This article discussed finding the number of elements greater than K in the range L to R using the Fenwick Tree. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

Check out this problem - Next Smaller Element

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavors, and Keep Coding.