Real-World Use

Segment trees and Fenwick trees are staples of coding interviews, but they also show up quietly in real systems wherever a changing sequence needs range summaries. This chapter covers where they appear, libraries you can use directly, and the most common mistakes.

Where they appear

• Compression and frequency tables: the Fenwick tree was originally proposed for arithmetic coding, which must repeatedly update symbol frequencies and look up "the cumulative frequency of all symbols before this one".
• Leaderboards and percentiles: store the number of players per score in a Fenwick tree and "how many players scored higher than me", that is, a rank, takes O(log n). When a score changes, subtract from the old slot and add to the new one.
• Time-series monitoring: dashboards that keep per-minute metrics in an array and repeatedly ask for the maximum or total over a window can back those questions with a segment tree.
• Computational geometry: sweep-line problems such as the area of a union of rectangles open and close intervals while a segment tree maintains "the length currently covered".
• Scheduling and booking: with a booking count per time slot, "the maximum number of concurrent bookings in this window" is a lazy segment tree supporting range add and range max.

A leaderboard example

class Leaderboard:
    """Scores are integers in 0..max_score. Rank = players with a higher score + 1."""

    def __init__(self, max_score):
        self.size = max_score + 1
        self.tree = [0] * (self.size + 1)
        self.scores = {}

    def _add(self, score, delta):
        i = score + 1
        while i <= self.size:
            self.tree[i] += delta
            i += i & -i

    def _count_at_most(self, score):
        i, total = score + 1, 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def set_score(self, player, score):
        if player in self.scores:
            self._add(self.scores[player], -1)
        self.scores[player] = score
        self._add(score, 1)

    def rank(self, player):
        higher = len(self.scores) - self._count_at_most(self.scores[player])
        return higher + 1


board = Leaderboard(1000)
for name, s in [("ana", 720), ("ben", 950), ("cho", 720), ("dev", 400)]:
    board.set_score(name, s)
print(board.rank("ana"), board.rank("ben"), board.rank("dev"))   # 2 1 4
board.set_score("dev", 990)
print(board.rank("dev"), board.rank("ben"))                      # 1 2

Libraries

Instead of writing your own, you can use a tested implementation. The AtCoder Library (ACL) provides segtree, lazy_segtree, and fenwick_tree for C++. You pass the operation and the identity as functions, which maps directly onto the monoid idea from the first chapter.

#include <atcoder/segtree>
#include <climits>
#include <iostream>
#include <vector>

int op(int a, int b) { return a < b ? a : b; }   // minimum
int e() { return INT_MAX; }                        // identity

int main() {
    std::vector<int> v = {5, 3, 7, 9, 6, 4, 1, 2};
    atcoder::segtree<int, op, e> seg(v);
    std::cout << seg.prod(2, 6) << '\n';   // minimum of [2, 6): 4
    seg.set(4, 0);
    std::cout << seg.prod(2, 6) << '\n';   // 0
    std::cout << seg.all_prod() << '\n';   // 0
}