Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Range-mode indexes: combine complete-block modes with fringe candidates

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A range mode is the most frequent value inside a subarray; this index breaks ties by choosing the smaller integer. The static readings array is divided into square-root-sized blocks. During construction, every pair of complete-block boundaries stores the mode of the covered core. A query adds all values in the two incomplete boundary fringes as candidates, then checks each candidate's exact occurrence count with binary searches in per-value position lists. Any global mode absent from the fringes must already be a mode of the complete core, which is why one stored core candidate suffices under the deterministic tie rule. Empty windows return no value. This lesson is for arbitrary modes, not only values occurring more than half the time.

Operational case

For readings [47,19,47,29,29,29,83,47,29,61,61,61,61], positions [0,6) have mode 29 and the last five positions have mode 61. The window [2,9) also returns 29. A shorter fringe-only query falls back to its own distinct values because no complete block lies inside it. If a mode occurs in a partial block, omitting boundary values from the candidate set can lose the answer. Query endpoints are half-open, and every stored position is zero-based. A changed reading invalidates the precomputed core modes and both old and new occurrence lists, so the model has no in-place update method.

Working Python program

python
from bisect import bisect_left
from collections import defaultdict
from math import isqrt


class StaticReadingModes:
    def __init__(self, readings):
        self.readings = list(readings)
        self.length = len(readings)
        self.block_size = max(1, isqrt(self.length))
        self.block_count = (self.length + self.block_size - 1) // self.block_size
        self.positions = defaultdict(list)
        for position, reading in enumerate(readings):
            if not isinstance(reading, int):
                raise TypeError("integer readings required")
            self.positions[reading].append(position)
        self.core_mode = [[None] * self.block_count for _ in range(self.block_count)]
        for first_block in range(self.block_count):
            frequency = defaultdict(int)
            best_value, best_count = None, 0
            for last_block in range(first_block, self.block_count):
                start = last_block * self.block_size
                stop = min(start + self.block_size, self.length)
                for position in range(start, stop):
                    value = self.readings[position]
                    frequency[value] += 1
                    count = frequency[value]
                    if count > best_count or (count == best_count and value < best_value):
                        best_value, best_count = value, count
                self.core_mode[first_block][last_block] = best_value

    def mode(self, start, stop):
        if not 0 <= start <= stop <= self.length:
            raise ValueError("invalid half-open range")
        if start == stop:
            return None
        first_full = (start + self.block_size - 1) // self.block_size
        after_last_full = stop // self.block_size
        if first_full < after_last_full:
            candidates = {self.core_mode[first_full][after_last_full - 1]}
            candidates.update(self.readings[start:first_full * self.block_size])
            candidates.update(self.readings[after_last_full * self.block_size:stop])
        else:
            candidates = set(self.readings[start:stop])
        def score(value):
            locations = self.positions[value]
            count = bisect_left(locations, stop) - bisect_left(locations, start)
            return count, -value
        return max(candidates, key=score)


mode_index = StaticReadingModes([47, 19, 47, 29, 29, 29, 83, 47, 29, 61, 61, 61, 61])
print("first six:", mode_index.mode(0, 6))
print("last five:", mode_index.mode(8, 13))
print("middle tie:", mode_index.mode(2, 9))

Output

Output
first six: 29
last five: 61
middle tie: 29

Time, space, and tradeoff

With N readings and B about sqrt N blocks, building every core interval by extending a frequency map takes O(NB) time and O(B squared) mode slots; occurrence lists use O(N) more space. A query examines at most O(sqrt N) fringe values plus one core value, and each frequency check takes O(log N), giving O(sqrt N log N) time and O(sqrt N) temporary candidate space. The implementation uses a fixed block size and Python dictionaries, so constant factors matter. A strict-majority index can answer a narrower question in O(log N) time; this one pays more to return a mode even when its frequency is small.

Common Mistakes

  • Do not assume a complete-block mode alone answers a query with fringes.
  • Do not treat a range mode as necessarily a strict majority.
  • Do not include the half-open right endpoint in occurrence counts.
  • Do not update the source array while retaining static core-mode tables.

Connected lessons

Compare this operation boundary with Count Sketch: estimate signed incident frequencies with row medians, Exponential histograms: estimate failures in a recent event window, then complete the structure audit and decision quiz.

data structures
range-query-structures
Storage details