Segment Trees and Fenwick Trees: Range Queries Made Fast

You have an array of numbers. You need to answer thousands of queries like "what's the sum of elements from index 3 to index 7?" and also update individual elements between queries. How fast can you do this?

The naive approach — just loop from index 3 to 7 and add them up — is O(n) per query. If you have Q queries on an array of size N, that's O(N * Q). For N = 100,000 and Q = 100,000, that's 10 billion operations. Way too slow.

Prefix sums get you O(1) queries, but then updates become O(n) because you need to rebuild the prefix array. You've traded one problem for another.

What you need is a data structure that handles both queries and updates efficiently. That's exactly what segment trees and Fenwick trees (also called Binary Indexed Trees) provide — O(log n) for both operations.

The Range Query Problem

Let's be precise about what we're solving:

Given: An array arr of n elements. Operations:

1. Range query: compute some function (sum, min, max, GCD, etc.) over elements arr[l] to arr[r]
2. Point update: change arr[i] to a new value

Goal: Both operations in O(log n) time.

Approach	Query	Update
Naive loop	O(n)	O(1)
Prefix sum	O(1)	O(n)
Segment tree	O(log n)	O(log n)
Fenwick tree	O(log n)	O(log n)

The segment tree is more general (works with any associative operation), while the Fenwick tree is simpler and has smaller constants (works best for sum and XOR).

Segment Tree: The Idea

A segment tree is a binary tree where:

• Each leaf represents a single element of the array


• Each internal node represents the result of a function over a range of elements


• The root represents the function over the entire array

For a sum segment tree over [1, 3, 5, 7, 9, 11]:

              [36]              (sum of all elements)
            /      \
         [9]        [27]        (sum of first/second half)
        /   \      /    \
      [4]   [5]  [16]   [11]   (smaller ranges)
      / \        /  \
    [1] [3]    [7]  [9]        (individual elements)

To answer "sum from index 2 to 4" (elements 5, 7, 9 = 21), you traverse the tree and combine only the nodes whose ranges fall within your query range. This takes O(log n) because the tree has O(log n) levels.

Building a Segment Tree

We typically store the segment tree in an array of size 4 n (safe upper bound), using the same indexing trick as binary heaps: node i's children are at 2i and 2*i+1.

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0]  (4  self.n)
        self._build(arr, 1, 0, self.n - 1)

def _build(self, arr, node, start, end):
        if start == end:
            # Leaf node
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self._build(arr, 2 * node, start, mid)        # left child
            self._build(arr, 2 * node + 1, mid + 1, end)  # right child
            self.tree[node] = self.tree[2  node] + self.tree[2  node + 1]

The build process is O(n) — each element is visited once, and each internal node is computed from its children.

Querying a Range

To query the sum of arr[l..r], we recursively check each node:

• If the node's range is completely inside [l, r], return its value


• If the node's range is completely outside [l, r], return 0 (identity for sum)


• Otherwise, split and recurse on both children

def query(self, l, r):
    return self._query(1, 0, self.n - 1, l, r)


def _query(self, node, start, end, l, r):
    if r < start or end < l:
        # Completely outside query range
        return 0
    if l <= start and end <= r:
        # Completely inside query range
        return self.tree[node]
    # Partial overlap — split
    mid = (start + end) // 2
    left_sum = self._query(2 * node, start, mid, l, r)
    right_sum = self._query(2 * node + 1, mid + 1, end, l, r)
    return left_sum + right_sum

At each level of the tree, at most two nodes have partial overlap (one on each boundary of the query range). So the query visits at most O(log n) nodes.

Updating a Point

To update arr[i], we find the leaf, update it, and propagate the change up to the root.

def update(self, i, val):
    self._update(1, 0, self.n - 1, i, val)

def _update(self, node, start, end, i, val):
    if start == end:
        # Leaf node — update it
        self.tree[node] = val
    else:
        mid = (start + end) // 2
        if i <= mid:
            self._update(2 * node, start, mid, i, val)
        else:
            self._update(2 * node + 1, mid + 1, end, i, val)
        # Recalculate this node from children
        self.tree[node] = self.tree[2  node] + self.tree[2  node + 1]

We only visit one node per level, so updates are O(log n).

Putting It All Together

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0]  (4  self.n)
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)

def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self._build(arr, 2 * node, start, mid)
            self._build(arr, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.tree[2  node] + self.tree[2  node + 1]

def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, l, r) +
                self._query(2 * node + 1, mid + 1, end, l, r))

def update(self, i, val):
        self._update(1, 0, self.n - 1, i, val)

def _update(self, node, start, end, i, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if i <= mid:
                self._update(2 * node, start, mid, i, val)
            else:
                self._update(2 * node + 1, mid + 1, end, i, val)
            self.tree[node] = self.tree[2  node] + self.tree[2  node + 1]

# Usage
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)

print(st.query(1, 3))   # sum of arr[1..3] = 3 + 5 + 7 = 15
st.update(2, 10)         # arr[2] = 10 (was 5)
print(st.query(1, 3))   # sum of arr[1..3] = 3 + 10 + 7 = 20

Lazy Propagation: Range Updates

What if you need to update a range instead of a single point? For example, "add 5 to every element from index 2 to 5."

Without optimization, you'd call point update for each index — O(n log n) per range update. Lazy propagation makes range updates O(log n) by deferring updates to children.

The idea: when you update a range, mark a node as "lazy" instead of immediately updating all its descendants. Only when you actually need to query or update a child do you push the lazy value down.

class LazySegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0]  (4  self.n)
        self.lazy = [0]  (4  self.n)
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)

def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self._build(arr, 2 * node, start, mid)
            self._build(arr, 2 * node + 1, mid + 1, end)
            self.tree[node] = self.tree[2  node] + self.tree[2  node + 1]

def _push_down(self, node, start, end):
        if self.lazy[node] != 0:
            mid = (start + end) // 2
            # Propagate to left child
            self.tree[2  node] += self.lazy[node]  (mid - start + 1)
            self.lazy[2 * node] += self.lazy[node]
            # Propagate to right child
            self.tree[2  node + 1] += self.lazy[node]  (end - mid)
            self.lazy[2 * node + 1] += self.lazy[node]
            # Clear lazy
            self.lazy[node] = 0

def range_update(self, l, r, val):
        self._range_update(1, 0, self.n - 1, l, r, val)

def _range_update(self, node, start, end, l, r, val):
        if r < start or end < l:
            return
        if l <= start and end <= r:
            # Entire range covered — apply lazily
            self.tree[node] += val * (end - start + 1)
            self.lazy[node] += val
            return
        self._push_down(node, start, end)
        mid = (start + end) // 2
        self._range_update(2 * node, start, mid, l, r, val)
        self._range_update(2 * node + 1, mid + 1, end, l, r, val)
        self.tree[node] = self.tree[2  node] + self.tree[2  node + 1]

def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

def _query(self, node, start, end, l, r):
        if r < start or end < l:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        self._push_down(node, start, end)
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, l, r) +
                self._query(2 * node + 1, mid + 1, end, l, r))

Lazy propagation is essential for competitive programming problems that involve range updates. Without it, many problems become unsolvable within time limits.

Fenwick Tree (Binary Indexed Tree)

The Fenwick tree solves the same problem as the segment tree but with a completely different approach. It's simpler, uses less memory (just an array of size n + 1), and has smaller constants — but it only works naturally with operations that have an inverse (like sum, where you can subtract to get a range from prefix sums).

The key insight is bitwise: each index i in the Fenwick tree stores the sum of a range of elements, and the range is determined by the lowest set bit of i.

• Index 1 (binary: 0001) stores arr[1] (range of 1)
• Index 2 (binary: 0010) stores arr[1] + arr[2] (range of 2)
• Index 3 (binary: 0011) stores arr[3] (range of 1)
• Index 4 (binary: 0100) stores arr[1] + arr[2] + arr[3] + arr[4] (range of 4)
• Index 5 (binary: 0101) stores arr[5] (range of 1)
• Index 6 (binary: 0110) stores arr[5] + arr[6] (range of 2)

The pattern: the lowest set bit of i tells you how many elements that position is responsible for.

Fenwick Tree Implementation

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)  # 1-indexed

@classmethod
    def from_array(cls, arr):
        """Build from array in O(n)"""
        n = len(arr)
        ft = cls(n)
        for i in range(n):
            ft.tree[i + 1] = arr[i]
        for i in range(1, n + 1):
            parent = i + (i & (-i))
            if parent <= n:
                ft.tree[parent] += ft.tree[i]
        return ft

def update(self, i, delta):
        """Add delta to arr[i] (1-indexed)"""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # move to parent

def prefix_sum(self, i):
        """Sum of arr[1..i]"""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # move to predecessor
        return total

def range_sum(self, l, r):
        """Sum of arr[l..r] (1-indexed)"""
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

# Usage
arr = [1, 3, 5, 7, 9, 11]
ft = FenwickTree.from_array(arr)

print(ft.range_sum(2, 4))  # sum of arr[2..4] = 3 + 5 + 7 = 15
ft.update(3, 5)             # arr[3] += 5 (5 -> 10)
print(ft.range_sum(2, 4))  # sum of arr[2..4] = 3 + 10 + 7 = 20

The magic is in the bit manipulation:

• i & (-i) gives the lowest set bit of i


• Adding the lowest set bit moves to the next responsible ancestor (for updates)


• Subtracting the lowest set bit moves to the next range to include (for queries)

Both operations visit at most O(log n) positions because each step removes or adds at least one bit.

When to Use Which

Use a Segment Tree when:

• You need range minimum/maximum queries (Fenwick can't do this naturally)
• You need lazy propagation for range updates
• You need to support complex merge operations (GCD, set union, etc.)
• The operation doesn't have a convenient inverse

Use a Fenwick Tree when:

• You need prefix sums or range sums
• You want simpler code with smaller constants
• Memory is tight (Fenwick uses N+1 space, segment tree uses 4N)
• You need to code it quickly in a competition

Performance comparison:

• Both are O(log n) for query and update
• Fenwick has smaller constants (roughly 2-3x faster in practice)
• Segment tree uses more memory but is more flexible
• Fenwick code is shorter and harder to get wrong

Competitive Programming Applications

These data structures appear constantly in competitive programming:

1. Inversion count — count pairs where i < j but arr[i] > arr[j] using a Fenwick tree
2. Range sum with updates — the classic application for both
3. Range minimum queries — segment tree with min() instead of +
4. Coordinate compression + offline queries — combine with sorting
5. 2D Fenwick tree — extend to 2D for matrix prefix sums with updates
6. Persistent segment tree — maintain all historical versions for time-travel queries

If you're preparing for competitive programming or coding interviews that involve range queries, start with the Fenwick tree (it covers most sum problems), then learn the segment tree (it covers everything else).

Common Mistakes

Off-by-one errors with Fenwick trees. Fenwick trees are 1-indexed. If your array is 0-indexed, add 1 when inserting and querying. This is the number one bug. Not allocating enough space for the segment tree. Use 4 n, not 2 n. The tree can have up to 4 * n - 5 nodes for some sizes. Forgetting to push down lazy values before recursing. In lazy segment trees, you must call push_down before visiting children in both queries and updates. Missing this produces silent wrong answers. Using Fenwick for min/max queries. The standard Fenwick tree only supports operations with inverses (sum, XOR). Min/max don't have convenient inverses. Use a segment tree instead.

What's Next

Segment trees and Fenwick trees are fundamental tools for any competitive programmer, and they show up in real systems too — database engines use similar structures for range indexes, and time-series databases use them for efficient aggregations.

Once you're comfortable with the basics, explore persistent segment trees (for versioned queries), merge sort trees (for order statistics), and 2D extensions. These are the building blocks that make hard problems tractable.

For more data structure and algorithm tutorials, check out CodeUp.