DSA Advanced Structures

Segment Tree

The analytics feed asks for sum on [L, R) after every click that edits one cell. Prefix sums die on updates. You need a structure whose combine is a .

Each node stores an aggregate for a segment. Queries glue O(log n) disjoint nodes using and . Range updates add a .

Algorithm journey

Name the monoid

combine + identity (+ optional lazy op).

Build bottom-up

Leaves = array; parents = combine.

Cover [L,R) with O(log n) nodes

Associativity makes order safe.

Point or lazy range update

Push tags before partial descent.

What actually happens

Naive idea: scan the range each query, or rebuild a prefix array after each update. At n=q=10⁵ that is ~10¹⁰ ops or Θ(n) rebuilds: both fail.

Better idea: store associative aggregates on a binary partition of the array. A query composes O(log n) canonical segments; a point update climbs O(log n) ancestors.

The improved design still fails for non-associative queries (median), wrong identities on padded leaves, or lazy tag composition bugs.

Invariant

Every node stores combine over its segment. After updates (and pushes), that claim stays true even if lazy descendants are stale: tags record exactly the deferred work.

How to choose a segment tree

1. Static invertible sums? Prefix sums beat everything.

2. Point updates + prefix/group ops? Fenwick is leaner.

3. General monoid / lazy ranges? Segment tree.

Quantitative check

n=10⁵, q=10⁵ mixed queries/updates: segment tree ~ q·log₂n ≈ 1.7×10⁶ combines vs naive q·n/2 ≈ 5×10⁹ scans.

Interactive range decomposition

Segment-tree monoid lab

Half-open range decomposition

i=0

i=1

i=2

i=3

i=4

i=5

query

sum[1,5) = 13

canonical nodes

node 9 + node 5 + node 12

contract

combine = + · identity = 0

Associativity lets the tree change parenthesization, not operand order. The canonical nodes remain left-to-right so noncommutative monoids are safe. Updates recompute one root-to-leaf path.

💻 Implementation (Range Sum)

Below is an iterative implementation of a Segment Tree for Range Sum Queries.

Python

python

class SegmentTree:
    """Iterative range-sum tree; public ranges are half-open [left, right)."""
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)
        self.tree[self.size:self.size + self.n] = data
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        if not 0 <= index < self.n:
            raise IndexError(index)
        i = self.size + index
        self.tree[i] = value
        i //= 2
        while i:
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
            i //= 2

    def query(self, left, right):
        if not 0 <= left <= right <= self.n:
            raise IndexError((left, right))
        left, right = left + self.size, right + self.size
        answer = 0
        while left < right:
            if left & 1:
                answer += self.tree[left]
                left += 1
            if right & 1:
                right -= 1
                answer += self.tree[right]
            left //= 2
            right //= 2
        return answer

tree = SegmentTree([2, 1, 5, 3, 4, 7])
assert tree.query(1, 5) == 13
tree.update(2, 8)
assert tree.query(1, 5) == 16

Java

java

class SegmentTree {
    private final int n, size;
    private final long[] tree;

    SegmentTree(long[] data) {
        n = data.length;
        int power = 1;
        while (power < n) power <<= 1;
        size = power;
        tree = new long[2 * size];
        System.arraycopy(data, 0, tree, size, n);
        for (int i = size - 1; i > 0; i--) {
            tree[i] = Math.addExact(tree[2 * i], tree[2 * i + 1]);
        }
    }

    void update(int index, long value) {
        if (index < 0 || index >= n) throw new IndexOutOfBoundsException(index);
        int i = size + index;
        tree[i] = value;
        for (i >>= 1; i > 0; i >>= 1) {
            tree[i] = Math.addExact(tree[2 * i], tree[2 * i + 1]);
        }
    }

    long query(int left, int right) {
        if (left < 0 || left > right || right > n) throw new IndexOutOfBoundsException();
        long answer = 0L;
        for (left += size, right += size; left < right; left >>= 1, right >>= 1) {
            if ((left & 1) == 1) answer = Math.addExact(answer, tree[left++]);
            if ((right & 1) == 1) answer = Math.addExact(answer, tree[--right]);
        }
        return answer;
    }

    public static void main(String[] args) {
        SegmentTree t = new SegmentTree(new long[]{2, 1, 5, 3, 4, 7});
        if (t.query(1, 5) != 13) throw new AssertionError();
        t.update(2, 8);
        if (t.query(1, 5) != 16) throw new AssertionError();
    }
}

The monoid contract

Value

Each leaf maps one array value into an aggregate type.

Associative combine

combine(combine(a,b),c) = combine(a,combine(b,c)); parenthesization may follow tree shape.

Identity

combine(identity,x)=x; disjoint query pieces and padded leaves return it.

Sum/0, min/+∞, max/−∞, gcd/0, and structured aggregates such as maximum-subarray tuples work. Median does not have a small associative summary. For noncommutative monoids (for example string concatenation), preserve left/right accumulation order in iterative queries.

Lazy propagation for range updates

Cover

A fully covered node absorbs the update without visiting leaves.

Tag

Store the deferred operation and update the node aggregate for its segment length.

Compose

New and old tags compose in a documented order; assignment and addition are not interchangeable.

Push

Before partial descent, propagate the tag to children and clear it at the parent.

Invariant: every node aggregate already reflects all updates covering its segment, even if descendants do not. Tags describe exactly the work descendants still need. Incorrect tag composition is the most common lazy-tree bug.

Coordinate compression and structure selection

Structure	Queries	Updates	Best fit
Prefix sums	O(1) invertible range sum	O(n)	Static sums
Fenwick tree	O(log n) prefix/range for group-like operations	O(log n) point	Compact sums/frequencies
Segment tree	O(log n) general monoid range	Point or lazy range	Flexible aggregates/updates
Sparse table	O(1) idempotent RMQ after O(n log n)	None	Immutable min/max/gcd

Coordinate compression: sort unique event coordinates and map them to ranks when only relative order matters. For interval lengths/coverage, preserve gaps explicitly: the distance between adjacent coordinates is not necessarily one.

Testing and production guardrails

• Standardize half-open [l,r) APIs; test empty/full/singleton ranges and n=0.
• Use long totals and define overflow policy.
• Test non-power-of-two sizes and padding identities.
• Cross-check random operations against a naive array oracle.

• For lazy trees, test overlapping/nested updates and tag order.
• Generic APIs should accept combine/identity and document mutability.
• Iterative 2·power-of-two layout improves locality; recursive 4n layout simplifies lazy logic.
• Persistent/dynamic trees trade allocations for versioning or sparse domains.

⚖️ Segment Tree vs. Fenwick Tree

Segment Tree:

More versatile (can do Min, Max, GCD)
Easier to understand conceptually
Allows range updates (with Lazy Propagation)

Fenwick Tree (BIT):

More space-efficient (O(N))
Simpler, less memory, and typically smaller constant factors
Primarily used for prefix sums

Short takeaway

A segment tree stores monoid aggregates on a binary partition of an array: O(log n) query and point update when combine is associative with an identity.

Exercises

Why can a segment tree compute range min but not range median with a constant-size node value?
For sum, what identity do padded leaves need, and what breaks if you leave them as garbage?
n=q=10⁵. Compare naive scans, Fenwick (sums only), and a segment tree for min queries with point updates.

Primary sources

Competitive programming handbooks: iterative segment trees and lazy propagation.
Cormen et al., CLRS: related range/tree ideas; monoid view is standard in CP literature.
Fenwick (BIT) papers/notes for the lighter prefix alternative.