AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 29

Part 7 · Advanced and Applied · Chapter 29

Advanced Structures: Segment Trees, Fenwick, LRU, Bloom

Four structures that show up the moment scale gets serious: range queries with updates, an O(1) cache, and a filter that is allowed to be wrong in exactly one direction.

Reading

CLRS Ch. 14 · Skiena 12

Focus

Structures under pressure

Cost

O(log n)

Needs

Trees, hashing

By the end of this chapter you can

Explain why a prefix-sum array fails as soon as updates are allowed
Build a segment tree and describe exactly which O(log n) nodes a query touches
Implement a Fenwick tree and explain what i & -i is doing
Build an LRU cache from a hash map plus a doubly linked list, with every operation O(1)
Describe a Bloom filter's error model and compute its false-positive rate
Choose the right structure for a given access pattern

1Range queries meet updates

Either of the two operations alone is easy. Wanting both at once is what forces you into a tree.

“What is the sum of elements 400 through 900?” is answered instantly by a prefix-sum array (Chapter 4): precompute pre[i] = a[0] + ... + a[i-1] once, then any range is pre[hi+1] - pre[lo] in O(1).

Now change one element. Every prefix sum after it is wrong, and repairing them is O(n).

Structure	Range query	Point update	Space
Plain array	O(n)	O(1)	n
Prefix-sum array	O(1)	O(n)	n
Segment tree	O(log n)	O(log n)	~4n
Fenwick (BIT)	O(log n)	O(log n)	n
Sqrt decomposition	O(√n)	O(1)	n + √n

A ledger versus a set of subtotals

A prefix-sum array is a ledger with a running balance written on every line. Reading any range is a subtraction. Correcting a single early entry means rewriting every line below it.

A segment tree is a set of subtotals arranged in a hierarchy: totals per day, per week, per month, per year. Changing one transaction updates its day, its week, its month and its year — four numbers, not four thousand. And any range you ask for can be assembled from a handful of those subtotals.

That is the trade the rest of this section makes concrete: give up O(1) queries to get O(log n) updates, and be far better off overall.

The sqrt decomposition in that table is worth a sentence, because it is the easiest of the four to write and is often enough: chop the array into blocks of √n, keep a total per block, and answer a query by walking the partial blocks at each end plus the whole blocks in between. Twenty lines, no recursion, and √100000 ≈ 316 is fast in practice.

2Segment trees

A binary tree over ranges. The root covers everything, each node splits its range in half, and the leaves are the elements.

Each internal node stores the combination of its two children — the sum, the minimum, the maximum, the GCD, whatever your operation is. Updating a leaf repairs the log n nodes on the path to the root; a query assembles the answer from at most 2 log n nodes.

segtree.pyno recursion, 2n memory

class SegmentTree:
    """Iterative, 1-indexed-internally, using the standard 2n array layout."""

    def __init__(self, data):
        self.n = len(data)
        self.t = [0] * (2 * self.n)
        self.t[self.n:] = data                       # leaves occupy the second half
        for i in range(self.n - 1, 0, -1):           # build parents bottom-up
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

    def update(self, i, value):
        i += self.n
        self.t[i] = value
        i //= 2
        while i:                                     # repair the path to the root
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
            i //= 2

    def query(self, lo, hi):
        """Sum of data[lo:hi] — half open."""
        total = 0
        lo += self.n
        hi += self.n
        while lo < hi:
            if lo & 1:                               # lo is a right child: take it, move on
                total += self.t[lo]
                lo += 1
            if hi & 1:                               # hi is a right child: take its left sibling
                hi -= 1
                total += self.t[hi]
            lo //= 2
            hi //= 2
        return total

Why a query touches only O(log n) nodes

Walk up from both ends of the range simultaneously. At each level you can absorb at most one node from the left boundary and one from the right, because everything strictly inside is covered by an ancestor you will reach next.

There are log n levels and at most two nodes taken per level, so the answer is always the combination of fewer than 2 log n stored values — about 34 nodes for a million elements.

What a segment tree can do that Fenwick cannot

The operation only has to be associative. Sum, min, max, GCD, matrix product, “the longest run of 1s in this range” — all fine.

Fenwick trees (next section) additionally need the operation to be invertible, because they answer a range by subtracting one prefix from another. There is no “un-minimum”, so range-minimum needs a segment tree.

Segment trees also extend to lazy propagation, where an update applies to a whole range: mark the node, defer the work to its children until someone actually looks. That gives O(log n) range updates as well as range queries, and it is the standard tool for “add 5 to everything between here and there”.

3Fenwick trees

The same asymptotics as a segment tree, in n words of memory and eight lines of code — at the price of one piece of bit arithmetic you have to take seriously for ten minutes.

A Fenwick tree, or binary indexed tree, stores partial sums at cleverly chosen positions: index i holds the sum of the i & -i elements ending at i.

fenwick.pyn words, eight lines

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)          # 1-indexed; t[0] is unused

    def add(self, i, delta):
        """Add delta to element i (0-indexed)."""
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i                 # move to the next node that covers i

    def prefix(self, i):
        """Sum of the first i elements."""
        total = 0
        while i > 0:
            total += self.t[i]
            i -= i & -i                 # strip the lowest set bit
        return total

    def range_sum(self, lo, hi):
        """Sum of data[lo:hi] — half open."""
        return self.prefix(hi) - self.prefix(lo)

i & -i is the lowest set bit

In two's complement, -i is ~i + 1, which flips every bit above the lowest set bit and leaves that bit alone. AND-ing the two therefore isolates exactly that bit:

  12 = 0b1100
 -12 = 0b0100  (as far as the low bits are concerned)
 12 & -12 = 4     <- the lowest set bit

So t[12] covers 4 elements: 9, 10, 11, 12. t[8] covers 8 elements, t[7] covers 1. Stripping the lowest set bit walks you down through a prefix in at most log n steps, because a number has at most log n set bits.

Paying with exact change

The prefix sum up to 13 is t[13] + t[12] + t[8], because 13 = 8 + 4 + 1 and each term covers a block of that size.

It is the same move as making 13 pence from coins of 8, 4 and 1: write the number in binary and each 1-bit is a coin you must hand over. The number of steps is the number of set bits, which is why the whole thing is O(log n) without any tree ever being built.

	Segment tree	Fenwick tree
Memory	2n to 4n	n
Code length	~30 lines	~8 lines
Constant factor	Higher	Very low
Sum, XOR, count	Yes	Yes
Min, max, GCD	Yes	No — not invertible
Range update	Yes, with lazy propagation	Only with two trees and some algebra
Reach for it when	The operation is exotic, or updates hit ranges	You need prefix sums and speed

Fenwick trees also solve the “count how many elements so far are smaller than x” problem, which is how you count inversions in O(n log n) without merge sort: sweep the array, and at each element ask the tree for the number of already-seen values greater than it, then add the element.

4LRU caches

Two conflicting requirements: find any key instantly, and know which key was used longest ago. One structure cannot do both, so use two.

A desk with limited space

Papers you use often stay on the desk; the rest go in the drawer, which is slow. When the desk is full and you need something new, you put away whatever you have not touched in the longest time.

To make that work you need two things at once: to find any paper instantly (an index), and to know which paper has been untouched longest (an order). A pile gives you the order but not the lookup; an index gives you the lookup but not the order.

So keep both, and make sure that touching a paper updates both in constant time.

The classic implementation is a hash map plus a doubly linked list. The map takes a key to its list node, so lookup is O(1). The list keeps the keys in recency order, and because it is doubly linked, any node can be unlinked and moved to the front in O(1) — which a singly linked list cannot do, since you would have to find the predecessor.

lru.pyevery operation O(1)

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head = Node()            # sentinels remove every edge case from the
        self.tail = Node()            # unlink/insert code — no None checks at all
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)            # touching it makes it the most recent
        self._push_front(node)
        return node.value

    def put(self, key, value):
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) >= self.cap:
            lru = self.tail.prev      # the node just before the tail sentinel
            self._unlink(lru)
            del self.map[lru.key]     # <- the eviction people forget
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

Three bugs, all common

Forgetting del self.map[lru.key]. The list shrinks, the map does not, and the cache silently grows without bound. This is why the evicted node must store its own key.
Not moving a node on get. A read is a use. Skip the reorder and you have built an LFU-ish thing that evicts recently-read entries.
Skipping the sentinels. They cost two nodes and remove every “is this the head?” branch from the unlink and insert code. Almost every LRU bug lives in those branches.

In Python you would use OrderedDict

collections.OrderedDict is a hash map plus a doubly linked list, in C:

from collections import OrderedDict

class LRUCache(OrderedDict):
    def __init__(self, cap): super().__init__(); self.cap = cap
    def get(self, k):
        if k not in self: return -1
        self.move_to_end(k); return self[k]
    def put(self, k, v):
        if k in self: self.move_to_end(k)
        self[k] = v
        if len(self) > self.cap: self.popitem(last=False)

And functools.lru_cache — which you used in Chapter 25 for memoisation — is exactly this structure with a function call as the key.

5Bloom filters

A set that answers 'definitely not present' or 'probably present', in a fraction of the memory. The asymmetry is the feature.

A guest list you can only stamp

Instead of writing down every guest's name, you keep a long row of boxes. When a guest arrives you compute three numbers from their name and stamp those three boxes.

Later, to check whether someone is on the list, compute their three numbers. If any of those boxes is blank, they were definitely never stamped in — a certain no. If all three are stamped, they are probably on the list, but it is possible three other guests stamped those boxes between them.

You cannot un-stamp a box, which is why a Bloom filter cannot support deletion: unstamping might erase evidence of somebody else.

bloom.py

class BloomFilter:
    def __init__(self, size, k):
        self.size = size
        self.k = k
        self.bits = 0                        # a Python int as an arbitrary-length bit vector

    def _positions(self, item):
        h = hash(item)
        h1 = h & 0xFFFFFFFF
        h2 = (h >> 32) & 0xFFFFFFFF or 0x9E3779B1
        # Kirsch-Mitzenmacher: k hashes from two, with no loss of accuracy
        return [(h1 + i * h2) % self.size for i in range(self.k)]

    def add(self, item):
        for p in self._positions(item):
            self.bits |= 1 << p

    def __contains__(self, item):
        return all((self.bits >> p) & 1 for p in self._positions(item))

The error model, precisely

False negatives are impossible. If an item was added, all its bits are set, so the query returns True. Always.
False positives are possible. Other items' bits can happen to cover all of yours.

With m bits, n items and k hash functions, the false-positive rate is about (1 - e^(-kn/m))^k, minimised at k = (m/n) · ln 2.

Concretely: about 10 bits per item and 7 hash functions gives roughly a 1% false-positive rate — and 10 bits is far less than storing a URL, an email address or a 32-byte hash. That ratio is the entire reason the structure exists.

Use	Why the asymmetry is acceptable
Database: skip a disk read	A false positive costs one wasted read; a false negative would lose data
Web cache: “have we seen this URL?”	Occasionally re-fetching is harmless
Spell-checker dictionary	Occasionally accepting a non-word is tolerable
Blocklists / malware URL sets	A rare false positive escalates to a real lookup
Distributed systems: set reconciliation	A cheap summary to send over the network

Where a Bloom filter would be wrong: any application in which a false positive is expensive or irreversible. “Have I already charged this customer?” must not be answered probabilistically.

The family it belongs to

Bloom filters are one of a set of probabilistic (sketch) structures that trade exactness for memory, and they all share the same pitch: an answer that is approximately right, in a fraction of the space, in one pass.

Counting Bloom filter — counters instead of bits, which restores deletion at 4× the space.
Count-Min sketch — approximate frequencies. “Roughly how many times has this IP hit us?”
HyperLogLog — the number of distinct items, to within ~2%, in a couple of kilobytes regardless of the count.
Cuckoo filter — Bloom-like, but supports deletion and is usually smaller at low error rates.

6Choosing under pressure

These four are what you reach for when the ordinary structures stop being enough. The trigger for each is specific.

The situation	The structure
Range sums, no updates	Prefix-sum array (Ch. 4)
Range sums with point updates	Fenwick tree
Range min/max/GCD with updates	Segment tree
Updates that hit whole ranges	Segment tree with lazy propagation
Counting inversions, or “how many so far are smaller”	Fenwick over value ranks
A bounded cache with recency eviction	Hash map + doubly linked list
Membership over a huge set, memory-bound	Bloom filter
Approximate counts / cardinality	Count-Min sketch / HyperLogLog
Something simple that is fast enough	Sqrt decomposition

The pattern shared by all four

Every structure in this chapter buys an improvement by giving something up, and naming the trade is more useful than memorising the code:

Segment tree: gives up O(1) queries to gain fast updates.
Fenwick: gives up general operations to gain memory and constant factor.
LRU: gives up single-structure simplicity to gain O(1) on both axes.
Bloom: gives up exactness — in one direction only — to gain an order of magnitude of memory.

When you meet a structure you have not seen, ask what it gave up. The answer usually tells you both how it works and when it is the wrong choice.

Instruments, not tools

You will not implement a segment tree at work this year. You may well need to know that “range query plus update” is a solved problem with a name, so that you can search for it rather than write an O(n) loop and wonder why the service is slow.

That recognition — this shape of problem has a structure — is what this chapter is for. Chapter 30 makes it the whole subject.

What to carry forward

A prefix-sum array gives O(1) range queries and O(n) updates. Wanting both fast is what forces a tree.
A segment tree stores a combined value per range. Update repairs one root path; a query assembles fewer than 2 log n stored nodes.
Segment trees need only an associative operation, so min, max and GCD all work. Lazy propagation adds O(log n) range updates.
A Fenwick tree does prefix sums in n words and eight lines, but needs an invertible operation — so no range-minimum.
i & -i isolates the lowest set bit. Adding it walks up, subtracting it walks down a prefix, in at most log n steps.
Fenwick over value ranks counts inversions in O(n log n) without merge sort.
An LRU cache is a hash map (for lookup) plus a doubly linked list (for recency). Both are needed; neither suffices alone.
Use sentinel head and tail nodes, move a node on get as well as put, and delete the evicted key from the map.
A Bloom filter never gives a false negative and sometimes gives a false positive. ~10 bits per item and 7 hashes gives about 1%.
Bloom filters cannot delete, because clearing a bit might erase another item's evidence.
Ask what a structure gave up. That tells you how it works and when not to use it.

>_Playground

A segment tree and a Fenwick tree racing a naive array, an LRU cache being exercised, and a Bloom filter's error rate measured against its formula.

scratch.pypython not loaded

import math, random, time
from collections import OrderedDict

random.seed(1)
N = 100000
DATA = [random.randint(0, 1000) for _ in range(N)]

# ---- three ways to answer the same two questions ---------------------------
class Naive:
    def __init__(self, data): self.a = list(data)
    def update(self, i, v): self.a[i] = v
    def query(self, lo, hi): return sum(self.a[lo:hi])

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.t = [0] * (2 * self.n)
        self.t[self.n:] = data
        for i in range(self.n - 1, 0, -1):
            self.t[i] = self.t[2*i] + self.t[2*i+1]
    def update(self, i, v):
        i += self.n; self.t[i] = v; i //= 2
        while i:
            self.t[i] = self.t[2*i] + self.t[2*i+1]; i //= 2
    def query(self, lo, hi):
        res = 0; lo += self.n; hi += self.n
        while lo < hi:
            if lo & 1: res += self.t[lo]; lo += 1
            if hi & 1: hi -= 1; res += self.t[hi]
            lo //= 2; hi //= 2
        return res

class Fenwick:
    def __init__(self, data):
        self.n = len(data)
        self.a = list(data)
        self.t = [0] * (self.n + 1)
        for i, v in enumerate(data):
            self._add(i, v)
    def _add(self, i, d):
        i += 1
        while i <= self.n:
            self.t[i] += d; i += i & -i
    def update(self, i, v):
        self._add(i, v - self.a[i]); self.a[i] = v
    def prefix(self, i):
        s = 0
        while i > 0:
            s += self.t[i]; i -= i & -i
        return s
    def query(self, lo, hi): return self.prefix(hi) - self.prefix(lo)

OPS = [(random.randrange(N), random.randint(0, 1000),
        *sorted(random.sample(range(N + 1), 2))) for _ in range(2000)]

print(f"{N:,} elements, {len(OPS):,} mixed update+query operations")
results = {}
for name, cls in (("naive array ", Naive), ("segment tree", SegmentTree), ("Fenwick tree", Fenwick)):
    st = cls(DATA)
    t = time.perf_counter()
    total = 0
    for i, v, lo, hi in OPS:
        st.update(i, v)
        total += st.query(lo, hi)
    dt = time.perf_counter() - t
    results[name] = total
    print(f"  {name}: {dt:7.3f}s   checksum {total}")
print("  all three agree:", len(set(results.values())) == 1)

# ---- what i & -i is doing ----------------------------------------------------
print()
print("  i    binary      i & -i   Fenwick node i covers this many elements")
for i in [1, 2, 3, 4, 6, 8, 12, 13, 16, 24]:
    print(f" {i:>3}   {i:>8b}   {i & -i:>6}   {i & -i}")
print()
print("prefix(13) reads nodes:", end=" ")
i = 13
while i > 0:
    print(i, end=" "); i -= i & -i
print("   (13 = 8 + 4 + 1)")

# ---- inversions, in O(n log n), without merge sort ---------------------------
def count_inversions(arr):
    rank = {v: i for i, v in enumerate(sorted(set(arr)))}
    n = len(rank)
    t = [0] * (n + 1)
    def add(i):
        i += 1
        while i <= n:
            t[i] += 1; i += i & -i
    def pref(i):
        s = 0
        while i > 0:
            s += t[i]; i -= i & -i
        return s
    inv = seen = 0
    for v in arr:
        r = rank[v]
        inv += seen - pref(r + 1)     # already-seen values strictly greater than v
        add(r); seen += 1
    return inv

def brute_inversions(a):
    return sum(1 for i in range(len(a)) for j in range(i+1, len(a)) if a[i] > a[j])

print()
for a in [[1,2,3], [3,2,1], [2,4,1,3,5], [1,1,1], [5,4,3,2,1]]:
    print(f"  inversions in {str(a):<18} = {count_inversions(a)}  (brute force: {brute_inversions(a)})")
big = [random.randint(0, 1000) for _ in range(50000)]
t = time.perf_counter(); iv = count_inversions(big); dt = time.perf_counter() - t
print(f"  50,000 random values: {iv:,} inversions in {dt:.3f}s "
      f"(brute force would be {50000*49999//2:,} comparisons)")

# ---- LRU -----------------------------------------------------------------------
class LRUCache:
    def __init__(self, cap):
        self.cap = cap; self.d = OrderedDict(); self.hits = self.misses = self.evictions = 0
    def get(self, k):
        if k not in self.d:
            self.misses += 1; return -1
        self.hits += 1; self.d.move_to_end(k); return self.d[k]
    def put(self, k, v):
        if k in self.d: self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap:
            self.d.popitem(last=False); self.evictions += 1

print()
c = LRUCache(3)
script = [("put","A",1), ("put","B",2), ("put","C",3), ("get","A",None),
          ("put","D",4), ("get","B",None), ("get","A",None), ("put","E",5), ("get","C",None)]
for op, k, v in script:
    if op == "put":
        c.put(k, v); note = f"put {k}"
    else:
        r = c.get(k); note = f"get {k} -> {r if r != -1 else 'MISS'}"
    print(f"  {note:<18} cache (oldest first): {list(c.d.keys())}")
print(f"  hits={c.hits} misses={c.misses} evictions={c.evictions}")

# hit rate depends entirely on the access pattern
def simulate(cap, keys):
    lru = LRUCache(cap)
    for k in keys:
        if lru.get(k) == -1:
            lru.put(k, k)
    return lru.hits / len(keys)

seq_scan = [i % 1000 for i in range(20000)]                 # cycles through 1000 keys
hot_cold = [random.choice(range(20)) if random.random() < 0.8
            else random.randrange(1000) for _ in range(20000)]
print()
print("  hit rate, capacity 100:")
print(f"    sequential scan of 1000 keys : {simulate(100, seq_scan):.1%}  "
      "<- LRU's worst case: it evicts exactly what is needed next")
print(f"    80/20 hot-key workload       : {simulate(100, hot_cold):.1%}")

# ---- Bloom: theory versus measurement ---------------------------------------
class Bloom:
    def __init__(self, size, k):
        self.size, self.k, self.bits = size, k, 0
    def _pos(self, x):
        h = hash(x) & 0xFFFFFFFFFFFFFFFF
        h1 = h & 0xFFFFFFFF
        h2 = (h >> 32) or 0x9E3779B1
        return [(h1 + i * h2) % self.size for i in range(self.k)]
    def add(self, x):
        for p in self._pos(x): self.bits |= 1 << p
    def __contains__(self, x):
        return all((self.bits >> p) & 1 for p in self._pos(x))

n = 5000
print()
print("Bloom filter: 5,000 items added, 20,000 absent items queried")
print("  bits/item   k   predicted FP   measured FP   memory vs. a set")
for bits_per in (4, 8, 10, 16, 24):
    m = n * bits_per
    k = max(1, round(bits_per * math.log(2)))
    bf = Bloom(m, k)
    for i in range(n):
        bf.add(f"item-{i}")
    fp = sum(1 for i in range(n, n + 20000) if f"item-{i}" in bf)
    pred = (1 - math.exp(-k * n / m)) ** k
    print(f"  {bits_per:>9}   {k}   {pred:>11.2%}   {fp/20000:>11.2%}   "
          f"{m//8:,} bytes vs ~{n*60:,}")

bf = Bloom(n * 10, 7)
for i in range(n):
    bf.add(f"item-{i}")
missing = [i for i in range(n) if f"item-{i}" not in bf]
print()
print(f"  false negatives among the 5,000 items actually added: {len(missing)}")
print("  ...and there never can be any. That is the whole guarantee.")

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 30 — Patterns, Interviews and the Capstone

Fifteen recognisable patterns, a procedure for attacking a problem you have never seen, and a capstone that makes you use eight structures in one system.

Continue →