Introduction

Given an array and many queries, scanning each range from left to right is often too slow. A better solution preprocesses the data so each query can quickly count how many values in positions L through R are greater than a threshold x.

The Problem and the Naive Baseline

Suppose you have an array values and queries shaped like (left, right, x). For each query, you need the count of elements in that index range whose value is strictly greater than x.

The direct approach is simple:

1def count_greater_naive(values, left, right, x):
2    count = 0
3    for i in range(left, right + 1):
4        if values[i] > x:
5            count += 1
6    return count
7
8
9values = [5, 1, 7, 3, 9, 2]
10print(count_greater_naive(values, 1, 4, 4))  # 2

This runs in linear time per query. If the array has n elements and you have many queries, the total cost can become too high.

Merge Sort Tree Approach

A practical data structure for this problem is a merge sort tree. It is a segment tree where each node stores the values of its segment in sorted order. To answer a query, you visit only the nodes that cover the requested range and use binary search in each node to count how many values are greater than x.

The preprocessing cost is O(n log n), and each query runs in O(log^2 n).

1from bisect import bisect_right
2
3
4class MergeSortTree:
5    def __init__(self, values):
6        self.n = len(values)
7        self.tree = [[] for _ in range(4 * self.n)]
8        self._build(values, 1, 0, self.n - 1)
9
10    def _build(self, values, node, left, right):
11        if left == right:
12            self.tree[node] = [values[left]]
13            return
14
15        mid = (left + right) // 2
16        self._build(values, node * 2, left, mid)
17        self._build(values, node * 2 + 1, mid + 1, right)
18
19        a = self.tree[node * 2]
20        b = self.tree[node * 2 + 1]
21        merged = []
22        i = j = 0
23
24        while i < len(a) and j < len(b):
25            if a[i] <= b[j]:
26                merged.append(a[i])
27                i += 1
28            else:
29                merged.append(b[j])
30                j += 1
31
32        merged.extend(a[i:])
33        merged.extend(b[j:])
34        self.tree[node] = merged
35
36    def query(self, ql, qr, x):
37        return self._query(1, 0, self.n - 1, ql, qr, x)
38
39    def _query(self, node, left, right, ql, qr, x):
40        if qr < left or right < ql:
41            return 0
42        if ql <= left and right <= qr:
43            values = self.tree[node]
44            return len(values) - bisect_right(values, x)
45
46        mid = (left + right) // 2
47        return (
48            self._query(node * 2, left, mid, ql, qr, x)
49            + self._query(node * 2 + 1, mid + 1, right, ql, qr, x)
50        )
51
52
53values = [5, 1, 7, 3, 9, 2]
54tree = MergeSortTree(values)
55print(tree.query(1, 4, 4))  # 2
56print(tree.query(0, 5, 6))  # 2

This is a strong choice when the array does not change and you need fast repeated queries.

Offline Queries With a Fenwick Tree

If updates are not required and all queries are known in advance, an offline strategy can be even cleaner. Sort array positions by value in descending order. Sort queries by x in descending order. As you move through the queries, activate every array position whose value is greater than the current x, then use a Fenwick tree to count how many active positions lie inside the requested index range.

That reduces each query to O(log n) after sorting. The main idea is that "greater than x" becomes a prefix of the values sorted in descending order.

This method is common in competitive programming because it is fast and memory-efficient, but it is less intuitive than a merge sort tree if you are learning the problem for the first time.

Choosing the Right Technique

Use the naive loop if the array is small or the number of queries is tiny. Use a merge sort tree when you want a reusable, query-friendly structure for many range requests. Use the offline Fenwick approach when all queries are available ahead of time and raw speed matters.

If the array also supports updates, the problem becomes harder. You would need a more advanced data structure such as a balanced binary indexed structure per segment, a wavelet tree, or a carefully designed ordered-statistics tree.

Common Pitfalls

• Forgetting whether the range endpoints are inclusive causes off-by-one errors immediately.
• Using bisect_left instead of bisect_right changes the behavior for values equal to x.
• Building a merge sort tree for an empty array needs a guard case to avoid invalid recursion.
• Assuming the offline method works for dynamic updates is incorrect because its preprocessing depends on fixed data.
• Confusing value order with index order breaks Fenwick tree solutions.

Summary

• The naive solution is easy but costs linear time per query.
• A merge sort tree preprocesses sorted values per segment and answers each query in O(log^2 n).
• An offline Fenwick tree solution can reduce query time to O(log n) when all queries are known in advance.
• Binary search details matter because the problem asks for values strictly greater than x.
• Pick the data structure based on whether the array is static, whether updates exist, and how many queries you need to answer.