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

Fenwick frequency index: select the kth stored key

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

A frequency Fenwick tree stores nonnegative counts at dense ranks of a known ordered key catalog. Insertion and removal change one count and all Fenwick summaries above it. To find the kth stored key, the search descends powers of two through the implicit prefix tree, skipping a candidate prefix only when its count is smaller than the remaining one-based rank. Duplicate keys consume multiple positions in rank order. A separate prefix count tells how many stored keys lie strictly below a threshold, even when the threshold itself is not in the catalog. The key universe is fixed here, although multiplicities may change. Negative multiplicity and an out-of-range selection are rejected before mutation.

Operational case

Declare allowed weights -35, 19, 4700, and 82000. Record shipments weighing 4700, -35, 4700, 19, and 82000. Sorted by weight, the third stored shipment weighs 4700; two shipments weigh less than 4700. Remove one 4700 shipment and the third still weighs 4700 because the other copy remains. This trace tests multiplicity and the one-based selection contract, not just unique-key ordering. A request for rank zero or rank five after removal is invalid. A previously unseen weight needs a rebuilt catalog and tree, so the example does not pretend that arbitrary keys can arrive without cost.

Working Python program

python
from bisect import bisect_left


class WeightOrderIndex:
    def __init__(self, allowed_weights):
        self.weights = sorted(set(allowed_weights))
        self.counts = [0] * len(self.weights)
        self.tree = [0] * (len(self.weights) + 1)
        self.total = 0

    def change(self, weight, delta):
        position = bisect_left(self.weights, weight)
        if position == len(self.weights) or self.weights[position] != weight:
            raise KeyError("weight not in declared catalog")
        if self.counts[position] + delta < 0:
            raise ValueError("weight count would become negative")
        self.counts[position] += delta
        self.total += delta
        cursor = position + 1
        while cursor < len(self.tree):
            self.tree[cursor] += delta
            cursor += cursor & -cursor

    def kth(self, one_based_rank):
        if not 1 <= one_based_rank <= self.total:
            raise IndexError("rank outside stored multiset")
        cursor = 0
        bit = 1 << (len(self.weights).bit_length() - 1)
        remaining = one_based_rank
        while bit:
            candidate = cursor + bit
            if candidate < len(self.tree) and self.tree[candidate] < remaining:
                remaining -= self.tree[candidate]
                cursor = candidate
            bit >>= 1
        return self.weights[cursor]

    def count_below(self, weight):
        cursor = bisect_left(self.weights, weight)
        total = 0
        while cursor:
            total += self.tree[cursor]
            cursor -= cursor & -cursor
        return total


if __name__ == "__main__":
    shipments = WeightOrderIndex([-35, 19, 4700, 82000])
    for weight in (4700, -35, 4700, 19, 82000):
        shipments.change(weight, 1)
    print("third=", shipments.kth(3), sep="")
    print("below-4700=", shipments.count_below(4700), sep="")
    shipments.change(4700, -1)
    print("third-after-removal=", shipments.kth(3), sep="")

Output

Output
third=4700
below-4700=2
third-after-removal=4700

Time, space, and tradeoff

Let U be the number of allowed distinct weights and M the number of recorded shipments. The initial sorted catalog costs O(U log U), and the Fenwick arrays use O(U) space. A count change, strict-below query, or kth selection takes O(log U) tree steps; finding a key's catalog position by binary search is also O(log U). The total stored multiplicity M does not enlarge the tree. Python integer arithmetic and comparisons add operand-size costs. An unsorted list gives cheap appends but expensive rank selection. A balanced search tree with subtree counts can admit new keys without rebuilding, at a more involved implementation cost. This fixed catalog favors a known key universe.

Common Mistakes

  • Do not use zero-based k when the selection API expects one-based rank.
  • Do not remove more copies than the multiset contains.
  • Do not let a negative count invalidate monotone prefix totals.
  • Do not treat an unknown weight as though it already has a Fenwick position.

Connected lessons

Compare with Coordinate compression: preserve order with dense integer ranks, Mo ordering: count distinct scan codes across an offline query batch, Two-dimensional prefixes: constant-time static rectangle sums, then run the query workload audit and contract quiz.

Span skip lists: rank and select without a full scan adds a related structure with a different operation boundary.

Alias tables: constant-work draws from fixed dispatch weights adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details