1.
Problem
2.
Approach
3.
Algorithm:
4.
C++ Code
4.1.
Output
5.
Algorithm Complexity
5.1.
Time Complexity
5.2.
Space Complexity
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

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

Jaglike Makkar

Problem

You are given an array ‘arr[]’ of length ‘N’. There is another array ‘queries[]’ of length Q. Each query is represented by three integers - L, R, and K. For each query, we must calculate the number of elements greater than K in the subarray starting from L to R.

Let’s understand the problem with the help of an example:

Input: N = 7, arr = [ 5, 3, 6, 2, 4, 7, 6 ], Q = 3, queries = [ {1, 4, 4}, {3, 7, 5}, {3, 7, 6} ]

Output: 2 3 1

Explanation:

1. For the first query, L = 1 and R = 4. Therefore the required subarray is - [ 5, 3, 6, 2 ]. In this subarray, we have to find the number of elements greater than K = 4. There are two such elements - 5 and 6. So, the number of elements greater than K for the first query is 2.
2. For the second query, L = 3 and R = 7. Therefore the required subarray is - [ 6, 2, 4, 7, 6 ]. In this subarray, we have to find the number of elements greater than K = 5. There are three such elements - 6, 7, and 6. So the number of elements greater than K for the second query is 3.
3. For the third query, L = 3 and R = 7. Therefore the required subarray is - [ 6, 2, 4, 7, 6 ]. Only one element greater than K = 6, i.e., 7. So the number of elements greater than K for the third query is 1.

Approach

The first thing that comes to mind for range queries is using the Fenwick tree or Segment tree. Let’s see if we can use them in this problem. We need to count the number of elements greater than K to store the count of all elements and find a way to count only the elements greater than K between ‘L’ and ‘R’.

First, we can combine both array elements and queries into a single data structure. Now we can iterate through the combined elements in reverse sorted order. For array elements, we can increase the count, and for query elements, only the elements greater than K would have been encountered till now.

Since we need the number of elements greater than K between ‘L’ and ‘R’, we can use a BIT where query(i) will return the number of elements present in the array until ith index. Therefore, the final answer will be query(‘R’) - query(‘L’-1).

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

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;
}
}

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.

Live masterclass