Number of elements less than or equal to a given number in a given subarray

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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]