Fenwick & Segment Trees

In Arrays & Dynamic Arrays you used prefix sums to answer "what is the total from day a to day b?" in O(1). That trick has one weakness: if a single value changes, every prefix total after it must be rebuilt, which is O(n). When data keeps changing and range questions keep coming, you need a structure where both operations are fast.

This advanced lesson introduces two such structures. A Fenwick tree (also called a binary indexed tree) handles sums with very little code. A segment tree is more general and also handles minimums, maximums and more. Both answer a range query and apply an update in O(log n).

The problem

A shop records daily sales. The manager asks range questions ("total for days 10 to 20?") but the accountant also corrects past days ("day 7 was actually ₹500 more"). Compare the options for n days:

With a lakh of days and a lakh of mixed operations, the first two methods can need up to 10⁵ × 10⁵ = 10¹⁰ steps in the worst case; the trees need about 10⁵ × 17 × 2, a few lakh.

Fenwick tree

A Fenwick tree stores a list tree (1-indexed for convenience) where each position holds the sum of a block of values. The size of the block at position i is decided by the lowest set bit of i, which is i & -i (see Bit Manipulation). For example, position 12 (1100 in binary) has lowest bit 4, so it stores the sum of 4 values: positions 9 to 12.

Two loops do all the work:

• prefix_sum(i): add tree[i], then jump to i - (i & -i), until i reaches 0. Each jump removes one 1 bit, so there are at most about log₂ n jumps.
• add(i, delta): add delta to tree[i], then jump to i + (i & -i), until past the end. These are exactly the positions whose blocks include i.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)            # index 0 is unused

    def add(self, i, delta):                 # value[i] += delta, i from 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

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

    def range_sum(self, a, b):
        return self.prefix_sum(b) - self.prefix_sum(a - 1)

sales = [12, 15, 9, 20, 18, 7, 25, 30, 11, 14]    # Rs thousands, days 1 to 10
fw = Fenwick(len(sales))
for day, amount in enumerate(sales, start=1):
    fw.add(day, amount)

print("Days 4-8:", fw.range_sum(4, 8))
fw.add(7, 5)                                      # correction: day 7 was 30, not 25
print("Days 4-8 after fix:", fw.range_sum(4, 8))
print("All 10 days:", fw.prefix_sum(10))

Days 4-8: 100
Days 4-8 after fix: 105
All 10 days: 166

Building the tree by calling add for every value is O(n log n); there is also an O(n) build, but this one is easier to remember. The whole structure is one list of n + 1 numbers.

How small is log n in practice? Count the loop steps for the worst positions in a tree of 10 lakh values:

def steps_query(i):
    s = 0
    while i > 0:
        i -= i & -i
        s += 1
    return s

def steps_update(i, n):
    s = 0
    while i <= n:
        i += i & -i
        s += 1
    return s

n = 1_000_000
print("worst query:", max(steps_query(i) for i in range(1, n + 1)))
print("worst update:", max(steps_update(i, n) for i in range(1, n + 1, 997)))

worst query: 19
worst update: 20

About 20 steps for a million values, whichever day you query or update.

Segment tree

A Fenwick tree relies on subtraction (a range is two prefixes subtracted), so it works for sums but not for minimums: you cannot "subtract" a minimum. A segment tree stores the answer for every segment directly. It is a binary tree where each leaf is one value and each internal node stores the combined answer (sum, min, max...) of its two children's ranges. The root covers everything.

A compact way to store it is an array of size 2n: leaves at positions n to 2n - 1, and node i's children at 2i and 2i + 1, with the root at position 1. To update, change a leaf and recompute its ancestors. To query a range, walk the two ends upwards, collecting nodes that lie fully inside the range.

Here a segment tree answers "what was the cheapest fare between day a and day b?" for train tickets whose prices change:

import math

class MinSegmentTree:
    def __init__(self, values):
        self.n = len(values)
        self.t = [math.inf] * (2 * self.n)
        self.t[self.n:] = values                      # leaves
        for i in range(self.n - 1, 0, -1):            # parents, bottom up
            self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])

    def update(self, pos, value):                     # pos from 0
        i = pos + self.n
        self.t[i] = value
        while i > 1:
            i //= 2
            self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])

    def query(self, left, right):                     # min of values[left..right]
        best = math.inf
        lo, hi = left + self.n, right + self.n + 1    # half-open [lo, hi)
        while lo < hi:
            if lo & 1:                                # lo is a right child: take it
                best = min(best, self.t[lo])
                lo += 1
            if hi & 1:                                # hi - 1 is a left boundary node
                hi -= 1
                best = min(best, self.t[hi])
            lo //= 2
            hi //= 2
        return best

fares = [1450, 1320, 1610, 1290, 1500, 1380, 1720, 1250]   # Rs, day 0 to 7
st = MinSegmentTree(fares)
print("Cheapest on days 0-3:", st.query(0, 3))
print("Cheapest on days 4-6:", st.query(4, 6))
st.update(5, 1199)                                         # a flash sale on day 5
print("Cheapest on days 4-6 after sale:", st.query(4, 6))
print("Cheapest overall:", st.query(0, 7))

Cheapest on days 0-3: 1290
Cheapest on days 4-6: 1380
Cheapest on days 4-6 after sale: 1199
Cheapest overall: 1199

Changing min to max, + or math.gcd (with a matching starting value: -math.inf, 0 or 0) turns the same code into a range maximum, range sum or range GCD tree. Any operation that is associative (grouping does not matter) works. Both update and query visit O(log n) nodes, and the tree uses O(n) memory.

Segment trees can do even more. With a technique called lazy propagation, they also support updates to a whole range at once ("add ₹100 to every fare from day 2 to day 6") in O(log n). That is beyond this course, but now you know the name to search for.

Common mistakes

• Mixing 0-based and 1-based indexes. The Fenwick tree above is 1-based; the segment tree is 0-based. Convert carefully at the boundary.
• Using a Fenwick tree for minimums. Prefix subtraction does not work for min or max; use a segment tree.
• Calling add with the new value instead of the difference. To set day 7 from 25 to 30, add 5.
• Choosing these trees when data never changes. A plain prefix sum list is simpler and faster.

Key points

• Prefix sums give O(1) queries but O(n) updates; Fenwick and segment trees give O(log n) for both.
• A Fenwick tree stores block sums sized by the lowest set bit, i & -i; it is short and fast for sums.
• A segment tree stores the combined answer for every segment and works for any associative operation, such as min, max and GCD.
• The iterative segment tree uses an array of size 2n with children at 2i and 2i + 1.
• Lazy propagation extends segment trees to range updates.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

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

    def range_sum(self, a, b):
        return self.prefix_sum(b) - self.prefix_sum(a - 1)

visitors = [120, 95, 140, 210, 180, 75, 160]
fw = Fenwick(7)
for day, v in enumerate(visitors, start=1):
    fw.add(day, v)

print(fw.range_sum(2, 5))
fw.add(3, 30)
print(fw.range_sum(2, 5), fw.prefix_sum(7))

625
655 1010