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

Range-majority indexes: verify a candidate before returning it

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

A range-majority index asks whether one value occurs more than half the time within a selected subarray. Each segment-tree node stores a candidate and a residual vote balance. Combining two summaries cancels opposing votes, preserving any true majority as a possible candidate. The summary alone is not proof: a candidate can remain after cancellation without exceeding half the range. This model stores sorted occurrence positions for every value, then uses two binary searches to count the candidate inside a half-open window. Its tree is immutable after construction, and values must be usable as dictionary keys. A zero-length window has no majority. Equality with half the window length does not qualify.

Operational case

Readings [47,19,47,47,83,19,47,61] give majority 47 over positions [0,5). The last four positions have no majority. The query for [3,3) returns none because it contains no readings. If a candidate occurs twice in a four-reading window, returning it would be wrong even if the vote summary carries a nonzero balance. Positions are zero-based and the right boundary is excluded. A correction to one stored reading would require repairing the segment tree and both affected position lists; this teaching index deliberately has no mutation method, avoiding a false constant-time update promise.

Working Python program

python
from bisect import bisect_left
from collections import defaultdict


def combine(left, right):
    left_candidate, left_balance = left
    right_candidate, right_balance = right
    if left_balance == 0:
        return right
    if right_balance == 0:
        return left
    if left_candidate == right_candidate:
        return left_candidate, left_balance + right_balance
    if left_balance > right_balance:
        return left_candidate, left_balance - right_balance
    return right_candidate, right_balance - left_balance


class MajorityWindowIndex:
    def __init__(self, readings):
        self.readings = list(readings)
        self.length = len(readings)
        self.base = 1 << max(0, self.length - 1).bit_length()
        self.tree = [(None, 0)] * (2 * self.base)
        self.positions = defaultdict(list)
        for index, reading in enumerate(readings):
            self.tree[self.base + index] = (reading, 1)
            self.positions[reading].append(index)
        for node in range(self.base - 1, 0, -1):
            self.tree[node] = combine(self.tree[2 * node], self.tree[2 * node + 1])

    def majority(self, start, end):
        if not 0 <= start <= end <= self.length:
            raise ValueError("invalid half-open window")
        left_accumulator = right_accumulator = (None, 0)
        left, right = start + self.base, end + self.base
        while left < right:
            if left & 1:
                left_accumulator = combine(left_accumulator, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                right_accumulator = combine(self.tree[right], right_accumulator)
            left //= 2
            right //= 2
        candidate, _ = combine(left_accumulator, right_accumulator)
        if candidate is None:
            return None
        locations = self.positions[candidate]
        occurrences = bisect_left(locations, end) - bisect_left(locations, start)
        return candidate if occurrences * 2 > end - start else None


majority_index = MajorityWindowIndex([47, 19, 47, 47, 83, 19, 47, 61])
print("first five:", majority_index.majority(0, 5))
print("last four:", majority_index.majority(4, 8))
print("empty:", majority_index.majority(3, 3))

Output

Output
first five: 47
last four: None
empty: None

Time, space, and tradeoff

Building tree summaries and occurrence lists costs O(N) time and space for N readings. A query combines O(log N) tree nodes and performs two binary searches in the candidate's occurrence list, giving O(log N) time and O(1) extra query space. The index finds a strict majority only; it does not enumerate every value above a lower frequency threshold. The segment summary is a compact candidate filter, and the position map supplies exact verification. A merge-sort tree can count values by threshold but stores more per-node sorted data for a broader set of questions.

Common Mistakes

  • Do not return a vote-cancellation candidate without counting its positions.
  • Do not treat exactly half the readings as a strict majority.
  • Do not include the half-open right boundary in occurrence counts.
  • Do not mutate source readings while keeping frozen position lists.

Connected lessons

Compare this operation boundary with Ordered treaps: split, join, and select depot keys, Span skip lists: rank and select without a full scan, Two-dimensional segment trees: correct sensors and sum rectangles, then complete the structure audit and decision quiz.

Range-mode indexes: combine complete-block modes with fringe candidates adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details