---
title: 'Segment and Fenwick Trees'
source: 'https://academia.sh/en/courses/data-structures/segment-trees'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:08:03+00:00'
license: 'CC BY-SA 4.0'
---

# Segment and Fenwick Trees

Situations that require both range queries and point updates together, the segment tree, and the Fenwick tree.

Suppose these two operations are performed repeatedly on an array of measurements:
ask for the sum of the values in a given range, and update a single value. If both
happen often, none of the structures covered so far give a good answer.

## Two Extreme Solutions

**Raw array.** An update is a single write: $O(1)$. A range sum, however, walks
every element in the range: $O(n)$.

**Prefix-sum array.** If the running totals from the start are precomputed, the sum
of any range is the difference of two values: $O(1)$. In exchange, when a single
value changes, every prefix sum after it must be recomputed: $O(n)$.

```python
measurements = [12, 18, 7, 25, 14, 30]

prefix_sums = [0] * (len(measurements) + 1)
for i, value in enumerate(measurements):
    prefix_sums[i + 1] = prefix_sums[i] + value

print(prefix_sums)                # [0, 12, 30, 37, 62, 76, 106]
print(prefix_sums[4] - prefix_sums[1])        # 50   — range 1..3: 18 + 7 + 25
```

Both solutions make one operation constant and the other linear. If both happen
often, neither is sufficient; what is needed is a structure that makes **both
operations logarithmic**.

## The Segment Tree

A **segment tree** divides the array in half, recursively: the root represents the
whole array, its children represent its halves, and their children represent
quarters. Every node stores a summary of its own range — here, its sum.

```
                [0..5] = 106
             /                \
        [0..2] = 37        [3..5] = 69
        /      \            /       \
   [0..1]=30  [2..2]=7  [3..4]=39  [5..5]=30
    /    \                 /   \
 [0]=12 [1]=18         [3]=25 [4]=14
```

A **query** expresses the requested range as a union of nodes in the tree. Any range
can be covered with at most $O(\log n)$ nodes; this is the source of the query cost.

An **update** changes the relevant leaf and recomputes every summary along the path
from the leaf to the root — again $O(\log n)$.

```python
class SegmentTree:
    """Range sum query and point update; both O(log n)."""

    def __init__(self, data: list[int]) -> None:
        self._n = len(data)
        self._tree = [0] * (2 * self._n)          # leaves occupy the second half
        for i, value in enumerate(data):
            self._tree[self._n + i] = value
        for i in range(self._n - 1, 0, -1):       # internal nodes, bottom-up
            self._tree[i] = self._tree[2 * i] + self._tree[2 * i + 1]

    def update(self, index: int, value: int) -> None:
        i = self._n + index
        self._tree[i] = value
        i //= 2
        while i >= 1:                             # refresh summaries up to the root
            self._tree[i] = self._tree[2 * i] + self._tree[2 * i + 1]
            i //= 2

    def range_sum(self, left: int, right: int) -> int:
        """Sum of the half-open range [left, right)."""
        result = 0
        l, r = self._n + left, self._n + right
        while l < r:
            if l % 2 == 1:                        # left bound is a right child: take it
                result += self._tree[l]
                l += 1
            if r % 2 == 1:                        # right bound is a right child: take it
                r -= 1
                result += self._tree[r]
            l //= 2
            r //= 2
        return result


tree = SegmentTree([12, 18, 7, 25, 14, 30])
print(tree.range_sum(0, 6))          # 106  — whole array
print(tree.range_sum(1, 4))          # 50   — 18 + 7 + 25
tree.update(2, 100)                  # 7 becomes 100
print(tree.range_sum(1, 4))          # 143
print(tree.range_sum(0, 6))          # 199
```

The generality of the structure stands out: the combining operation can be maximum,
minimum, greatest common divisor, or any operation with the associative property,
instead of sum. Only the summary stored in the nodes and the combining line change.

## The Fenwick Tree

A **Fenwick tree** (binary indexed tree) is a more compact structure concerned only
with prefix sums. It does the same job with a single array of $n$ slots; it uses
half the memory of a segment tree, and its code is noticeably shorter.

The idea is that each index stores the sum of a specific range, and the length of
that range is determined by the **lowest set bit** in the index's binary
representation. The `x & -x` idiom from the How Computers Work course is used
directly here.

```python
class FenwickTree:
    """Prefix sum and point update; O(log n)."""

    def __init__(self, size: int) -> None:
        self._tree = [0] * (size + 1)            # 1-based index

    def add(self, index: int, increment: int) -> None:
        i = index + 1
        while i < len(self._tree):
            self._tree[i] += increment
            i += i & -i                          # next responsible index

    def prefix_sum(self, index: int) -> int:
        """Sum of the range [0, index)."""
        result, i = 0, index
        while i > 0:
            result += self._tree[i]
            i -= i & -i                          # drop the lowest set bit
        return result

    def range_sum(self, left: int, right: int) -> int:
        return self.prefix_sum(right) - self.prefix_sum(left)


fenwick = FenwickTree(6)
for i, value in enumerate([12, 18, 7, 25, 14, 30]):
    fenwick.add(i, value)

print(fenwick.prefix_sum(6))            # 106
print(fenwick.range_sum(1, 4))          # 50
fenwick.add(2, 93)                      # 7 + 93 = 100
print(fenwick.range_sum(1, 4))          # 143
```

The Fenwick tree takes updates as an **increment**; to set a value directly, the
difference from the old value is added. This follows from the structure's
prefix-sum-oriented design.

## Which Structure, When

| Structure | Range query | Point update | Memory | Generality |
|---|---|---|---|---|
| Raw array | $O(n)$ | $O(1)$ | $n$ | Full |
| Prefix-sum array | $O(1)$ | $O(n)$ | $n$ | Sum only |
| Segment tree | $O(\log n)$ | $O(\log n)$ | $2n$ | Any associative operation |
| Fenwick tree | $O(\log n)$ | $O(\log n)$ | $n$ | Sum and operations with an inverse |

Selection criteria:

- If the data does not change, a **prefix-sum array** is best; no extra structure is
  needed.
- If only the total is queried, **Fenwick** is sufficient: less memory, shorter code.
- If operations without an inverse, such as minimum or maximum, or range updates are
  needed, a **segment tree** is used.

An extension of the segment tree makes range updates logarithmic as well: the
update is not propagated downward immediately but is kept at the node as a "pending
change" and applied only once that subtree is descended into. This technique is
covered in advanced algorithm topics.

## Uses

Range queries are a common need for systems that work with time series and ordered
data: the sum or maximum of measurements in a time interval, the number of records
in a given range of a ranking, counting objects in a region of a game world.

If the data does not change, the same questions are answered with precomputed
summaries; the reason these structures exist is that the data **keeps changing**.

## Summary

- A raw array makes updates constant, and a prefix-sum array makes queries constant;
  if both are needed often, neither is sufficient.
- A segment tree divides the array in half and stores a summary of each subrange at
  every node; query and update are $O(\log n)$.
- Any range can be covered with at most a logarithmic number of nodes.
- By changing the combining operation, the same structure is used for minimum,
  maximum, or other associative operations.
- A Fenwick tree is concerned only with prefix sums; it gives the same cost with
  half the memory and shorter code.
- The reason these structures exist is that the data changes; for static data,
  precomputed summaries suffice.

## Next Step

Range queries were one-dimensional: indices sat on a line. If positional data has
two or more dimensions — points on a map, records in a feature space — how does the
splitting idea extend? The next lesson covers this topic's final structure:
multidimensional trees.