Given an array of N integers, and a number of queries. Each query is represented by three integers: l (the starting index), r (the ending index, inclusive), and k. The task is to calculate how many elements in the subarray [l, r] (inclusive) are greater than k. Solve this efficiently for multiple queries.
Input: array =[1,4,2,6,8], queries =[(1,3,3),(0,4,5)]Output: [2,2]Explanation:
For (1,3,3): The subarray is[4,2,6]. Elements greater than 3:[4,6], count =2.For(0,4,5): The subarray is[1,4,2,6,8]. Elements greater than 5:[6,8], count =2.
Input: array =[10,20,30,40], queries =[(0,2,15),(1,3,25)]Output: [2,1]Explanation:
For (0,2,15): Subarray is[10,20,30]. Elements greater than 15:[20,30], count =2.For(1,3,25): Subarray is[20,30,40]. Elements greater than 25:[30,40], count =1.
publicclassSolution {
public List<Integer>countGreaterThanK(int[] arr, int[][] queries) {
List<Integer> result =new ArrayList<>();
// Process each queryfor (int[] query : queries) {
int l = query[0];
int r = query[1];
int k = query[2];
int count = 0;
// Iterate over subarray [l, r]for (int i = l; i <= r; i++) {
if (arr[i]> k) {
count++;
}
}
result.add(count);
}
return result;
}
publicstaticvoidmain(String[] args) {
Solution sol =new Solution();
int[] arr = {1, 4, 2, 6, 8};
int[][] queries = {
{1, 3, 3},
{0, 4, 5}
};
// Output the results for the queries System.out.println(sol.countGreaterThanK(arr, queries)); // Output: [2, 2] }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
defcountGreaterThanK(self, arr, queries):
result = []
for l, r, k in queries:
count =0# Iterate over the subarray [l, r]for i in range(l, r +1):
if arr[i] > k:
count +=1 result.append(count)
return result
# Example usage:arr = [1, 4, 2, 6, 8]
queries = [(1, 3, 3), (0, 4, 5)] # List of queriessol = Solution()
output = sol.countGreaterThanK(arr, queries)
print(output) # Output: [2, 2]
Using a Fenwick Tree (also known as a Binary Indexed Tree or BIT) is a powerful technique for solving range queries efficiently, especially when preprocessing helps achieve better performance than direct iteration. Below is the solution using Fenwick Tree.
The Fenwick Tree enables us to maintain and query frequencies across ranges efficiently. Here’s how we adapt the problem:
Preprocessing: Create a Fenwick Tree to maintain a frequency count of numbers in the array. For each number x in the array, we store its frequency in the Fenwick Tree (indexed at x or adjusted for range if numbers aren’t naturally bounded).
Answering Queries: For each query (l, r, k), we:
Query the cumulative frequency range for numbers greater than k within indices [l, r] by adjusting the Fenwick Tree structure.
This approach makes it possible to preprocess and answer range-based queries in logarithmic time for both updates and queries.
Coordinate compression (if needed): Fenwick Tree indices depend on naturally bounded values. If array values are large or sparse, coordinate compression maps array values to smaller integer ranges.
Fenwick Tree constructs a 1D structure to process range sums.
classFenwickTree {
privateint size;
privateint[] tree;
// Constructor to initialise Fenwick TreepublicFenwickTree(int size) {
this.size= size;
this.tree=newint[size + 1]; // Fenwick Tree indices are 1-based }
// Update the frequency of a number at 'index' by 'value'publicvoidupdate(int index, int value) {
while (index <= size) {
tree[index]+= value;
index += index &-index; // Move to the next index }
}
// Query cumulative frequency up to 'index'publicintquery(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index &-index; // Move to the parent node }
return sum;
}
// Query range [left, right]publicintrangeQuery(int left, int right) {
return query(right) - query(left - 1);
}
}
publicclassSolution {
public List<Integer>countGreaterThanK(int[] arr, int[][] queries) {
// Step 1: Coordinate compression TreeSet<Integer> uniqueVals =new TreeSet<>();
for (int val : arr) {
uniqueVals.add(val);
}
List<Integer> sortedVals =new ArrayList<>(uniqueVals);
Map<Integer, Integer> mapping =new HashMap<>();
for (int i = 0; i < sortedVals.size(); i++) {
mapping.put(sortedVals.get(i), i + 1); // Map values to compressed indices (1-based) }
// Step 2: Initialize Fenwick Treeint maxIndex = sortedVals.size();
FenwickTree fenwick =new FenwickTree(maxIndex);
// Step 3: Populate Fenwick Tree with array valuesfor (int val : arr) {
int compressedIndex = mapping.get(val);
fenwick.update(compressedIndex, 1); // Add frequency for the number }
// Step 4: Process each query List<Integer> result =new ArrayList<>();
for (int[] query : queries) {
int l = query[0];
int r = query[1];
int k = query[2];
int count = 0;
// Find compressed index for K Integer kCompressed = mapping.get(k);
// Query for range: All values greater than kif (kCompressed !=null) {
count = fenwick.query(maxIndex) - fenwick.query(kCompressed);
}
result.add(count);
}
return result;
}
publicstaticvoidmain(String[] args) {
Solution sol =new Solution();
int[] arr = {1, 4, 2, 6, 8};
int[][] queries = {
{1, 3, 3},
{0, 4, 5}
};
// Output the results for queries System.out.println(sol.countGreaterThanK(arr, queries)); // Output: [2, 2] }
}
classFenwickTree:
def __init__(self, size):
# Fenwick Tree size is based on the maximum value of the array self.size = size
self.tree = [0] * (size +1)
defupdate(self, index, value):
# Update the frequency of 'index' by 'value'while index <= self.size:
self.tree[index] += value
index += index &-index
defquery(self, index):
# Get the cumulative frequency up to 'index' sum =0while index >0:
sum += self.tree[index]
index -= index &-index
return sum
defrange_query(self, left, right):
# Query the cumulative frequency in range [left, right]return self.query(right) - self.query(left -1)
classSolution:
defcountGreaterThanK(self, arr, queries):
# Step 1: Coordinate compression for large values sorted_vals = sorted(set(arr)) # Unique sorted values mapping = {val: idx +1for idx, val in enumerate(sorted_vals)} # Map values to indices# Step 2: Initialize Fenwick Tree max_index = len(sorted_vals) # Size of compressed value range fenwick = FenwickTree(size=max_index)
# Step 3: Populate Fenwick Tree with array valuesfor val in arr:
compressed_val = mapping[val]
fenwick.update(compressed_val, 1) # Add frequency of the number in Fenwick Tree# Step 4: Process each query result = []
for l, r, k in queries:
# Find bounds in the compressed range for querying left = l +1# Convert 0-based to 1-based for coordinates right = r +1# Convert 0-based to 1-based for coordinates# Start query with numbers greater than K; count =0# Find the index in the compressed range for k# If K is greater than all array values, count will be 0if k in mapping:
k_compressed = mapping[k]
else:
count =0 result.append(count)
continue# Query for range: all values greater than `k` count = fenwick.query(max_index) - fenwick.query(k_compressed)
result.append(count)
return result
# Example usagearr = [1, 4, 2, 6, 8]
queries = [(1, 3, 3), (0, 4, 5)]
sol = Solution()
output = sol.countGreaterThanK(arr, queries)
print(output) # Output: [2, 2]