Activity Range Queries: Two Pointers, Bisect & Fenwick Tree

The Problem

Every user's activity is stored as a list of timestamps: dict[user_id, list[timestamp]]. The recurring question is "how many of this user's events fall in [start, end]" — asked once, asked repeatedly for many different ranges, or asked at different granularities (a per-minute range, a per-hour range, a per-day range). A minute-window query and a day-window query are not different algorithms — they're the exact same range-count operation with a wider or narrower [start, end], so none of the granularity language below implies switching techniques.

What actually changes the right technique is the access pattern, not the window size:

• Need the count for every window in a whole sequence of consecutive, fixed-size windows over data that's already fully collected? Two-pointer sweep.
• Need arbitrary, unpredictable one-off range queries over data that's already fully collected? Bisect (binary search on a sorted list).
• New events keep arriving, interleaved with arbitrary range queries, so the data can't be treated as static? Fenwick tree.

The rest of this page works through all three, then compares them directly.

Two-Pointer Sweep

If the events are already sorted (a single O(n log n) sort, done once) and the question is "give me the count for every window in a whole sequence of consecutive, fixed-size windows" — every hourly bucket across a day, every 10-minute bucket across a shift — a single forward sweep answers all of them at once. Two pointers, left and right, track the boundaries of the current window into the sorted timestamp list. For each successive window, left advances past any timestamp that's aged out of the new window's start, and right advances to include any timestamp that's now inside the new window's end. Both pointers only ever move forward.

That last sentence is the entire mechanism, and it's also the single most common way this pattern gets silently broken: left and right must stay monotonic across the entire pass over every window, never reset back to the start of the array for the next window. Reset them per-window and each window becomes an independent O(n) (or O(log n) with bisect) scan, turning what should be one O(n) pass into O(n × number of windows) — quadratic in disguise, because it still "looks like" a two-pointer solution. Kept monotonic, each pointer visits each index at most once across the whole run, regardless of how many windows there are.

Worked Example: Counting Events in Three Consecutive 10-Minute Windows

Sorted timestamps (minutes since start): [1, 3, 4, 7, 9, 12, 15, 16, 20, 23, 26, 29]. Sweep three consecutive, fixed-size windows of 10 minutes each: [0,10), [10,20), [20,30).

Notice left starts window 2 at 5 (exactly where window 1 left it) and right starts window 3 at 8 (exactly where window 2 left it) — neither pointer ever rewinds. The full 12-element list is touched by left and by right a total of one pass each across all three windows combined, not three separate passes. Counts: 5 + 3 + 4 = 12, matching the total number of events, since the three windows exactly tile [0, 30) with no gaps or overlaps.

Code

def sweep_fixed_windows(timestamps, window_size, num_windows):
    sorted_timestamps = sorted(timestamps)
    n = len(sorted_timestamps)
    left = 0
    right = 0
    results = []
    for w in range(num_windows):
        start = w * window_size
        end = start + window_size
        # advance left past anything before this window's start --
        # never reset to 0, or this silently becomes O(n) per window
        while left < n and sorted_timestamps[left] < start:
            left += 1
        # advance right to the first index at or past this window's end
        while right < n and sorted_timestamps[right] < end:
            right += 1
        count = right - left
        results.append((start, end, left, right, count))
    return results

Complexity

O(n log n) for the one-time sort, plus O(n) for the entire sweep across every window — not O(n) per window. Both pointers together make at most 2n total advances across the whole run, no matter how many windows are swept. Reach for a different technique the moment the queries stop being a sequence of consecutive, fixed-size windows and become arbitrary one-off ranges — see Bisect below.

Examples in This Set

Same technique family as #11 (sliding-window rate limiter, monotonic eviction from the front of a deque) and #15 (sliding window maximum) — both rely on the same "pointers only ever move forward across the whole run" discipline.

Bisect (Binary Search)

If the events are sorted once (O(n log n), one time) but the queries are arbitrary and unpredictable — not a tidy sequence of consecutive fixed-size windows, just "how many events fell between this specific start and end" for whatever range someone asks about next — binary search answers each one in O(log n) without ever touching the elements strictly inside the range. Python's bisect module makes this a one-liner: bisect_right(sorted_list, end) - bisect_left(sorted_list, start). bisect_left finds the leftmost index where start could be inserted to keep the list sorted (i.e. the first element >= start); bisect_right finds the rightmost such index for end (i.e. the first element > end). The gap between those two boundary positions is exactly the count of elements in [start, end] — only two O(log n) searches for boundaries, never an O(n) scan of the range's contents.

From-Scratch Implementation

Matching the rest of this site, here's bisect_left and bisect_right implemented from first principles rather than taken as a black box, verified below to match Python's built-in bisect module exactly.

def bisect_left(sorted_list, target):
    lo, hi = 0, len(sorted_list)
    while lo < hi:
        mid = (lo + hi) // 2
        if sorted_list[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def bisect_right(sorted_list, target):
    lo, hi = 0, len(sorted_list)
    while lo < hi:
        mid = (lo + hi) // 2
        # the only difference from bisect_left: <= instead of <
        if sorted_list[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

That single operator flip (< vs <=) is the entire difference between the two functions, and it's precisely what changes "leftmost insertion point" into "rightmost insertion point." When sorted_list[mid] == target, bisect_left treats it as "not yet past the target" and keeps hi pinned at mid, converging on the first occurrence of target. bisect_right treats that same equal element as "still allowed to insert after," pushing lo past it, so it converges just past the last occurrence of target. Neither function ever compares two list elements to each other — only each midpoint against target — which is what keeps every step O(1) and the whole search O(log n).

Worked Example: Verifying Against the Built-In, and Tracing the Steps

Sorted timestamps: [2, 5, 5, 8, 11, 14, 14, 14, 19, 23]. Running the from-scratch implementation against Python's bisect.bisect_left/bisect.bisect_right for every target from 0 to 25, and for a handful of range-count queries, confirms an exact match — see the Code section below for the raw output. Here's the internal lo/ hi/mid trace for two of those calls:

So count_in_range(start=5, end=14) = bisect_right(list, 14) - bisect_left(list, 5) = 8 - 1 = 7 — the 7 elements 5, 5, 8, 11, 14, 14, 14 — matching both the from-scratch and built-in implementations exactly.

Code and Verification Output

import bisect

sorted_timestamps = [2, 5, 5, 8, 11, 14, 14, 14, 19, 23]

for target in range(0, 26):
    assert bisect_left(sorted_timestamps, target) == bisect.bisect_left(sorted_timestamps, target)
    assert bisect_right(sorted_timestamps, target) == bisect.bisect_right(sorted_timestamps, target)

def count_in_range(sorted_list, start, end, bl, br):
    return br(sorted_list, end) - bl(sorted_list, start)

for start, end in [(5, 14), (0, 4), (14, 14), (6, 22)]:
    scratch = count_in_range(sorted_timestamps, start, end, bisect_left, bisect_right)
    builtin = count_in_range(sorted_timestamps, start, end, bisect.bisect_left, bisect.bisect_right)
    print(start, end, scratch, builtin, scratch == builtin)

Actual output (all 26 targets and all 4 range queries matched, no assertion failures):

target=14 bisect_left scratch=5 builtin=5 | bisect_right scratch=8 builtin=8 | match=True
total mismatches across all targets 0..25: 0

range [5,14] -> scratch=7 builtin=7 match=True
range [0,4] -> scratch=1 builtin=1 match=True
range [14,14] -> scratch=3 builtin=3 match=True
range [6,22] -> scratch=6 builtin=6 match=True

Complexity

O(log n) per arbitrary query, after an O(n log n) one-time sort. The hard precondition: sorted_list must already be sorted. Bisect does zero verification of that — it silently returns a wrong (but plausible-looking) insertion point on unsorted input, not an error. There's no way to tell from the return value alone that the input was unsorted.

Examples in This Set

#46 (count handle-time subarrays) solves a related "count things matching a cumulative condition" problem via a prefix-sum + hashmap, not bisect — that problem needs an exact-sum match rather than a range, and its inputs can be negative, which is exactly the situation where bisect's sorted-order requirement stops being usable and a hashmap of prefix sums takes over instead.

Fenwick Tree (Binary Indexed Tree)

Both techniques above assume the data is fully collected before any query runs — sort once, query many times. That assumption breaks the moment new events keep arriving, interleaved with range queries that need up-to-date answers. Inserting into a sorted list to keep bisect valid costs O(n) per insert, since every element after the insertion point has to shift over. A Fenwick tree (Binary Indexed Tree) gives up bisect's ability to answer against arbitrary raw values, in exchange for O(log n) inserts and O(log n) range queries simultaneously — exactly the tradeoff a streaming, interleaved workload needs.

The tree is conceptually an array of counts over fixed index buckets (e.g. "count of events in minute-bucket 7"), but it's stored so that each index is responsible for summing a specific contiguous range of buckets ending at itself, and that range's size is exactly determined by the index's lowest set bit (its binary representation's rightmost 1). update(i, delta) walks up the tree, repeatedly adding the current index's lowest set bit (i += i & (-i)) to move to the next index whose responsibility range also covers i, propagating the delta into every ancestor bucket. prefix_sum(i) walks down, repeatedly subtracting the lowest set bit (i -= i & (-i)) to accumulate the sum of a strictly shrinking set of non-overlapping responsibility ranges that together cover [0, i]. Both walks take O(log n) steps, since each step's lowest-set-bit jump at least doubles or halves the relevant bit position — the walk can't take more steps than the tree has bits.

Code

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, i, delta=1):
        # 1-indexed; walk up flipping the lowest set bit each step
        i += 1
        while i <= self.size:
            self.tree[i] += delta
            i += i & (-i)

    def prefix_sum(self, i):
        # sum of indices [0, i] (0-indexed input)
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)
        return total

    def range_sum(self, lo, hi):
        # inclusive [lo, hi], 0-indexed
        if lo == 0:
            return self.prefix_sum(hi)
        return self.prefix_sum(hi) - self.prefix_sum(lo - 1)

Worked Example: Streaming Inserts Interleaved With Queries

10 one-minute buckets, indices 0-9. Events arrive one at a time and queries are issued in between inserts, not batched after all inserts complete:

By step 10, six events have been inserted (minutes 2, 5, 2, 7, 5, 9) and range_sum(0, 9) correctly reports 6 — verified against a brute-force count over the raw event list at every query step (steps 3, 5, 8, 10 all matched exactly; see Code and Verification Output below). The tree never needed rebuilding or re-sorting between inserts and queries — each operation is an independent O(log n) walk.

Code and Verification Output

ft = FenwickTree(10)
events_so_far = []
ops = [
    ("insert", 2), ("insert", 5), ("query", (0, 9)),
    ("insert", 2), ("query", (0, 4)),
    ("insert", 7), ("insert", 5), ("query", (5, 9)),
    ("insert", 9), ("query", (0, 9)),
]
for action, arg in ops:
    if action == "insert":
        ft.update(arg, 1)
        events_so_far.append(arg)
    else:
        lo, hi = arg
        fenwick_result = ft.range_sum(lo, hi)
        brute_result = sum(1 for e in events_so_far if lo <= e <= hi)
        print(lo, hi, fenwick_result, brute_result, fenwick_result == brute_result)

Actual output:

step 3: fenwick=2 brute_force=2 match=True
step 5: fenwick=2 brute_force=2 match=True
step 8: fenwick=3 brute_force=3 match=True
step 10: fenwick=6 brute_force=6 match=True

Complexity

O(log n) per update, O(log n) per range_sum query, O(n) space for the underlying tree array (one entry per bucket index, plus the 1-indexing offset).

Handling Minutes/Hours/Days With One Tree

Bucket at the finest granularity any query will ever need — per-minute, in this example — and answer coarser queries by passing wider bucket-index ranges into the exact same tree: an hourly query is just range_sum(hour_start_minute, hour_start_minute + 59), a daily query is the same idea with a 1440-minute span. There's no need for separate trees per granularity; the underlying counts are identical regardless of how wide a window the caller happens to be asking about. A separate precomputed-rollup caching layer on top of the same tree only becomes worth the extra complexity if query volume is extreme enough that even O(log n) per query is too slow — not a default choice.

Which One When

Common Pitfalls