Problem

Given an array arr[] and a number of queries q, where each query is represented by l, r, x, your task is to print the number of elements less than or equal to x in the subarray from index l to r.

Examples

Example 1:

Input: arr = [1, 3, 5, 7, 9], queries = [(1, 3, 6), (0, 4, 8)]
Output: [2, 4]
Explanation:
- For the first query (1, 3, 6): subarray is [3, 5, 7], there are 2 elements (3 and 5) ≤ 6.
- For the second query (0, 4, 8): subarray is [1, 3, 5, 7, 9], there are 4 elements (1, 3, 5, and 7) ≤ 8.

Solution

Method 1 - Extract the subarray

Here is the approach:

  1. For each query, extract the subarray from l to r from the original array.
  2. Count the number of elements in the subarray that are less than or equal to x.

Code

Java
public class Solution {
 
    public List<Integer> processQueries(int[] arr, List<int[]> queries) {
	    List<Integer> res = new ArrayList<>();
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            int x = query[2];
            
            int count = 0;
            for (int i = l; i <= r; i++) {
                if (arr[i] <= x) {
                    count++;
                }
            }
	        res.add(count);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        List<int[]> queries = Arrays.asList(
            new int[]{1, 3, 6},
            new int[]{0, 4, 8}
        );

        new Solution().processQueries(arr, queries);
    }
}
Python
class Solution:
    def process_queries(self, arr: List[int], queries: List[Tuple[int, int, int]]) -> None:
        for l, r, x in queries:
            count = sum(1 for i in range(l, r+1) if arr[i] <= x)
            print(count)

# Example usage
sol = Solution()
arr = [1, 3, 5, 7, 9]
queries = [(1, 3, 6), (0, 4, 8)]
sol.process_queries(arr, queries)

Complexity

  • ⏰ Time complexity: O(q*n) where q is number of queries, and n is number of elements in arr
  • 🧺 Space complexity: O(1)

Method 2 - Using Binary Indexed Tree

To optimize the query processing, we can use the Binary Indexed Tree (BIT) or Fenwick Tree along with coordinate compression:

  1. Compress Coordinates: Map all numbers in the array to a compressed range to reduce the size of the BIT.
  2. Build BIT: Construct the Binary Indexed Tree using the compressed values.
  3. Processing Queries: For each query, use the Binary Indexed Tree to efficiently count the numbers within the given range that are less than or equal to x.

Code

Java
public class Solution {
    private static class BIT {
        private int[] BIT;
        private int n;

        public BIT(int n) {
            this.n = n;
            this.BIT = new int[n + 1];
        }

        public void update(int index, int val) {
            for (; index <= n; index += (index & -index)) {
                BIT[index] += val;
            }
        }

        public int query(int index) {
            int sum = 0;
            for (; index > 0; index -= (index & -index)) {
                sum += BIT[index];
            }
            return sum;
        }
    }

    public List<Integer> processQueries(int[] arr, List<int[]> queries) {
        int n = arr.length;
        List<Integer> result = new ArrayList<>();

        // Step 1: Coordinate compression
        int[] temp = Arrays.copyOf(arr, n);
        Arrays.sort(temp);
        Map<Integer, Integer> compressed = new HashMap<>();
        for (int i = 0; i < n; i++) {
            compressed.put(temp[i], i + 1);
        }

        // Step 2: Build the BIT
        BIT bit = new BIT(n);
        int[] BITree = new int[n + 1];
        for (int num : arr) {
            bit.update(compressed.get(num), 1);
        }

        // Step 3: Process each query
        for (int[] query : queries) {
            int l = query[0], r = query[1], x = query[2];
            int count = 0;
            // Compute the count of elements ≤ x in the range [1, r+1]
            for (int i = l; i <= r; i++) {
                if (arr[i] <= x) {
                    count += bit.query(compressed.get(arr[i]));
                }
            }
            result.add(count);
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 3, 5, 7, 9};
        List<int[]> queries = Arrays.asList(
            new int[]{1, 3, 6},
            new int[]{0, 4, 8}
        );
        List<Integer> result = solution.processQueries(arr, queries);
        System.out.println(result); // Expected output: [2, 4]
    }
}
Python
class BIT:
    def __init__(self, n: int):
        self.size = n
        self.tree = [0] * (n + 1)

    def update(self, index: int, value: int) -> None:
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def query(self, index: int) -> int:
        sum = 0
        while index > 0:
            sum += self.tree[index]
            index -= index & -index
        return sum

class Solution:
    def process_queries(self, arr: List[int], queries: List[Tuple[int, int, int]]) -> List[int]:
        n = len(arr)
        result = []

        # Step 1: Coordinate compression
        sorted_unique = sorted(set(arr))
        position = {num: idx + 1 for idx, num in enumerate(sorted_unique)}

        # Step 2: Build the BIT
        bit = BIT(len(sorted_unique))
        compressed_arr = [position[num] for num in arr]
        for num in compressed_arr:
            bit.update(num, 1)

        # Step 3: Process each query
        for l, r, x in queries:
            count = 0
            # Compute the count of elements ≤ x in the range [l, r]
            for i in range(l, r + 1):
                if arr[i] <= x:
                    count += bit.query(position[arr[i]])
            result.append(count)

        return result

# Example usage
sol = Solution()
arr = [1, 3, 5, 7, 9]
queries = [(1, 3, 6), (0, 4, 8)]
result = sol.process_queries(arr, queries)
print(result)  # Expected output: [2, 4]

Complexity

  • ⏰ Time complexity: O((n + q) log n)
    • Building the BIT takes O(n log n).
    • Each query takes O(log n), so for q queries the complexity is O(q log n).
  • 🧺 Space complexity: O(n) for the BIT and the arrays for coordinate compression.