Range Count Query

Range count (e.g., count of values ≤ k) often uses merge sort tree, Fenwick on coordinates, or segment tree with sorted vectors at nodes.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Offline: sort queries with Mo’s. Online with values: coordinate compress + Fenwick per segment tree node (merge sort tree).

Try this in Python

from bisect import bisect_right


def range_count_le(arr: list[int], l: int, r: int, k: int) -> int:
    return sum(1 for i in range(l, r + 1) if arr[i] <= k)


arr = [2, 1, 4, 3, 2]
print(range_count_le(arr, 0, 4, 2))

Common mistakes

• O(n) scan per query on large q.
• Forgetting compression when values up to 1e9.

Key takeaways

• Start with frequency array if values small.
• Merge sort tree: O(log² n) per query typical.