Data Structures & Algorithms / Optimization proofs and maintained aggregates / Lesson 16

Fenwick and segment range structures

Preserve a public half-open contract while maintaining logarithmic point updates and range aggregation.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Static prefixes and dynamic updates need different storage
Fenwick nodes store low-bit-sized suffix blocks
A segment tree combines disjoint interval pieces

Static prefixes and dynamic updates need different storage

A static prefix sum answers ranges efficiently but a changed element can invalidate many later entries. Fenwick and segment trees maintain selected aggregates so updates repair only logarithmically many pieces. Define whether an update adds a delta or assigns a new value. These are different operations: assigning7 to an existing5 requires delta2 in an additive structure. Both examples expose zero-based elements and half-open [left,right) queries, even though their internal indexing differs. Negative values are valid for sums. Do not infer that every range operation has the same algebra or supports the same inverse trick.

Fenwick nodes store low-bit-sized suffix blocks

Using one-based internal index i, a Fenwick cell stores the sum of a block ending at i with length i & -i. A prefix query subtracts that low bit to remove a disjoint final block; repeating reaches zero. An update adds the low bit to visit larger blocks containing the changed position. The first program converts a public zero-based position to i=index+1 before updating, preventing the nonprogressing internal zero case. Its constructor uses repeated point additions, so building this particular example is O(n log n), not the linear-build variant available with another construction.

python Self-contained Python3 algorithm example using synthetic local data.

class Fenwick:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (self.n + 1)
        for index, value in enumerate(values):
            self.add(index, value)
    def add(self, index, delta):
        if not 0 <= index < self.n:
            raise ValueError("Invalid element index")
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i
    def prefix(self, end):
        if not 0 <= end <= self.n:
            raise ValueError("Invalid prefix end")
        total, i = 0, end
        while i:
            total += self.tree[i]
            i -= i & -i
        return total
    def range_sum(self, left, right):
        if not 0 <= left <= right <= self.n:
            raise ValueError("Invalid half-open range")
        return self.prefix(right) - self.prefix(left)

tree = Fenwick([4, -2, 5, 1])
print(tree.range_sum(1, 3))
tree.add(1, 3)
print(tree.range_sum(1, 3))
print(tree.range_sum(0, 4))

Expected output

3
6
11

Adding3 changes the second value from-2 to1. Prefix differences remain correct after logarithmic aggregate repairs.

A segment tree combines disjoint interval pieces

The second program pads leaves to a power of two, stores sums above them, and assigns one leaf before recomputing ancestors. A range query moves two boundary cursors upward, adding a node only when its whole represented interval belongs to the requested range. Every selected piece is disjoint, preventing double counting. Construction is linear in padded leaf count, which is less than twice n for positive n. Point assignment and range sum take O(log n) work, with O(n) storage. The empty-input representation still allocates a neutral root but rejects every element assignment.

python Self-contained Python3 algorithm example using synthetic local data.

class SegmentSum:
    def __init__(self, values):
        self.n = len(values)
        self.base = 1
        while self.base < self.n:
            self.base *= 2
        self.tree = [0] * (2 * self.base)
        self.tree[self.base:self.base + self.n] = values
        for i in range(self.base - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    def assign(self, index, value):
        if not 0 <= index < self.n:
            raise ValueError("Invalid element index")
        i = self.base + index
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    def range_sum(self, left, right):
        if not 0 <= left <= right <= self.n:
            raise ValueError("Invalid half-open range")
        left += self.base
        right += self.base
        total = 0
        while left < right:
            if left & 1:
                total += self.tree[left]
                left += 1
            if right & 1:
                right -= 1
                total += self.tree[right]
            left //= 2
            right //= 2
        return total

tree = SegmentSum([4, -2, 5, 1])
print(tree.range_sum(1, 3))
tree.assign(1, 1)
print(tree.range_sum(1, 3))
print(tree.range_sum(0, 4))

Expected output

3
6
11

Assignment to1 matches the first example’s delta3 only because the old value was-2. The APIs deliberately expose different update meanings.

The aggregate operation determines valid formulas

Prefix subtraction works for additive sums because an inverse removes an earlier contribution. A minimum aggregate generally cannot subtract an earlier minimum to obtain an arbitrary range minimum. Segment trees require an associative combination and an identity for empty pieces; operations such as string concatenation also require preserving left-to-right order during queries. The single total accumulator here is suitable for commutative sum, not a universal template for every monoid. Range updates with lazy propagation add further invariants and are not provided by these point-update implementations. Do not claim an unsupported operation because the structure is called a tree.

Bounds and numeric semantics remain public obligations

Reject negative indices and reversed ranges before internal arithmetic, even though Python might otherwise accept negative indexing. prefix(0) and range_sum(k,k) legitimately return zero. The examples use exact integer sums; floating accumulation can have rounding behavior different from a direct scan because the addition grouping changes. Very large Python integers also change arithmetic cost. If the application caches original values to turn assignment into delta, update that cache under the same owner as the tree. A stale cached value can corrupt later assignments while every low-bit loop remains structurally correct.

Use a plain array as the mutation oracle

For short arrays, perform a sequence of point additions or assignments in both the structure and a plain reference list. After every mutation, compare every valid half-open range with sum(reference[left:right]). Include empty and singleton input, non-power-of-two lengths, negative deltas, final-element updates, and invalid bounds. This exposes indexing and stale-value defects more effectively than testing only the full sum. Keep tests finite and tiny. The low-bit and disjoint-piece arguments establish why the structure generalizes; no external database, live analytics system, or load benchmark is needed.

Common errors and fixes

A Fenwick update at internal zero never advances

Why it happens: The public zero-based index was not translated.
How to fix it: Start internal updates at index+1.
Prevent it next time: Test the first element and loop-progress invariant.

Assignment is accidentally treated as addition

Why it happens: The update API’s meaning was not documented.
How to fix it: Use a delta or a true assignment implementation consistently.
Prevent it next time: Assign the same value twice and compare a plain list.

Prefix minima are subtracted for range minima

Why it happens: The inverse property of sums was generalized incorrectly.
How to fix it: Choose an aggregate structure whose algebra supports the query.
Prevent it next time: Test a minimum located outside the requested interval.

Check your understanding

1. Why does i & -i make progress in a valid internal Fenwick update?

Show worked solution

For positive i it is a positive power of two, so adding it strictly increases i until it exceeds n. At i=0 it is zero, which explains the danger of failing to convert the public index. The query subtracts the same positive block size until reaching zero.

2. Can the segment-tree query be reused unchanged for ordered string concatenation?