# Segment Tree and Fenwick Tree — Range Queries with Updates

Source: https://skills101.in/learn/dsa/dsa-segment-tree-fenwick-tree — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

In the prefix sums lesson we answered "what is the sum of `a[L..R]`?" in O(1) after an O(n) setup. That works only while the array **never changes**. Now imagine a placement-test leaderboard: marks change whenever a student submits again, and the website keeps asking for the total marks of students ranked 20 to 60. If one value changes, every prefix sum after it changes too, so each update costs O(n). This lesson shows two structures that make **both** operations O(log n).

## 1. The trade-off

| Method | Update one value | Sum of a range |
|---|---|---|
| Plain array | O(1) | O(n) — add them up |
| Prefix sum array | O(n) — rebuild the rest | O(1) |
| Segment tree | O(log n) | O(log n) |
| Fenwick tree (BIT) | O(log n) | O(log n) |

With n = 10⁵ values and 10⁵ mixed updates and queries, the first two rows need on the order of 10¹⁰ steps in the worst case. The last two need a few million.

## 2. Segment tree: the idea

A **segment tree** is a binary tree where every node stores the answer (here, the sum) for one **segment** (a continuous range) of the array:

- the **root** covers the whole array `[0..n − 1]`;
- a node covering `[lo..hi]` has two children: the left half `[lo..mid]` and the right half `[mid + 1..hi]`;
- the **leaves** are single elements.

![Segment tree of sums for the array 5 2 6 1 3 4 7 8: the root holds 36, the leaves hold the array values, and the green nodes for 2..3, 4..5 and 6..6 together cover the query range 2 to 6 with sum 21](https://skills101.in/learn-img/dsa/segment-tree.svg)

**Query** `sum(L, R)`: start at the root.

- If the node's range is completely **outside** `[L..R]`, return 0.
- If it is completely **inside**, return its stored sum — no need to go deeper.
- Otherwise split: ask both children and add.

In the picture, `sum(2, 6)` uses only three nodes: `[2..3] = 7`, `[4..5] = 7` and `[6..6] = 7`, total 21. It can be shown that any range is covered by at most about 2 nodes per level, so a query visits **O(log n)** nodes.

**Update** `a[i] = x`: change the leaf, then fix the sums on the path back up to the root — one node per level, O(log n).

## 3. Segment tree code

We store the tree in an array like a heap: node `k` has children `2k` and `2k + 1`. An array of size `4n` is always big enough.

```python
class SegTree:
    def __init__(self, a):
        self.n = len(a)
        self.t = [0] * (4 * self.n)
        self._build(a, 1, 0, self.n - 1)

    def _build(self, a, k, lo, hi):
        if lo == hi:
            self.t[k] = a[lo]
            return
        mid = (lo + hi) // 2
        self._build(a, 2 * k, lo, mid)
        self._build(a, 2 * k + 1, mid + 1, hi)
        self.t[k] = self.t[2 * k] + self.t[2 * k + 1]

    def update(self, i, x, k=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if lo == hi:
            self.t[k] = x
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self.update(i, x, 2 * k, lo, mid)
        else:
            self.update(i, x, 2 * k + 1, mid + 1, hi)
        self.t[k] = self.t[2 * k] + self.t[2 * k + 1]

    def query(self, L, R, k=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if R < lo or hi < L:              # completely outside
            return 0
        if L <= lo and hi <= R:           # completely inside
            return self.t[k]
        mid = (lo + hi) // 2
        return self.query(L, R, 2 * k, lo, mid) + self.query(L, R, 2 * k + 1, mid + 1, hi)

st = SegTree([5, 2, 6, 1, 3, 4, 7, 8])
print(st.query(2, 6), st.query(0, 7))
st.update(3, 10)                          # a[3]: 1 -> 10
print(st.query(2, 6), st.query(3, 3))
```

```text
21 36
30 10
```

**Other operations.** Change the two `+` signs and the "outside" value and the same tree answers other questions. For **range minimum**, combine with `min` and return infinity for "outside". It works for any operation that can be combined in pieces, such as max, gcd or xor. (For adding a value to a **whole range** at once there is a further trick called **lazy propagation**; it is a topic for later practice.)

## 4. Fenwick tree (binary indexed tree)

A **Fenwick tree**, also called a **binary indexed tree (BIT)**, does sums with far less code. It uses 1-based indexes and one array `T`. The trick is the **lowest set bit** of `i`, written `i & −i`:

- `T[i]` stores the sum of the last `i & −i` elements ending at `i`.
- For example, 6 is `110` in binary, its lowest set bit is 2, so `T[6] = a[5] + a[6]`. 8 is `1000`, so `T[8]` covers all of `a[1..8]`.

![Fenwick tree ranges for indexes 1 to 8: entries 1, 3, 5 and 7 cover one item, entries 2 and 6 cover two, entry 4 covers four and entry 8 covers all eight; prefix(7) adds entries 7, 6 and 4](https://skills101.in/learn-img/dsa/fenwick-ranges.svg)

- **Prefix sum up to i:** add `T[i]`, then jump `i −= i & −i`, until `i` is 0. For 7: T[7] + T[6] + T[4].
- **Add x at position i:** add `x` to `T[i]`, then jump `i += i & −i`, until past `n`. Every block that contains position `i` gets updated.
- **Range sum L..R** = `prefix(R) − prefix(L − 1)`, exactly like prefix sums.

Each jump removes or adds one bit, so both loops run at most about log₂ n times.

```java
public class Main {
    static long[] T;
    static int n;

    static void add(int i, long x) {           // a[i] += x  (1-based)
        for (; i <= n; i += i & -i) T[i] += x;
    }

    static long prefix(int i) {                // a[1] + ... + a[i]
        long s = 0;
        for (; i > 0; i -= i & -i) s += T[i];
        return s;
    }

    static long rangeSum(int l, int r) {
        return prefix(r) - prefix(l - 1);
    }

    public static void main(String[] args) {
        int[] a = {5, 2, 6, 1, 3, 4, 7, 8};
        n = a.length;
        T = new long[n + 1];
        for (int i = 0; i < n; i++) add(i + 1, a[i]);

        System.out.println(prefix(7));          // 5+2+6+1+3+4+7
        System.out.println(rangeSum(3, 7));     // same range as [2..6] 0-based
        add(4, 9);                              // a[4] goes from 1 to 10
        System.out.println(rangeSum(3, 7));
        System.out.println(6 & -6);
    }
}
```

```text
28
21
30
2
```

Note that a Fenwick tree **adds** to a position. To **set** `a[i] = x`, keep a copy of the array and add `x − a[i]`.

## 5. Which one to use?

| | Segment tree | Fenwick tree |
|---|---|---|
| Code length | longer | very short |
| Memory | about 4n | n + 1 |
| Sum, count | yes | yes |
| Min / max over any range | yes | not directly |
| Range updates | with lazy propagation | with a second tree (advanced) |

A good rule: for sums and counts, write a Fenwick tree. For min, max or anything more unusual, write a segment tree. If the array never changes, plain prefix sums are still the simplest answer.

## Common mistakes

- Using a segment tree when no updates happen — prefix sums are enough.
- Making the tree array only `2n` long for the recursive version; use `4n`.
- Returning 0 for "outside" in a **min** tree; it must be infinity, or every minimum becomes 0.
- Using index 0 in a Fenwick tree: `0 & −0` is 0, so the loop never moves. Fenwick trees are 1-based.
- Calling `add(i, x)` when you meant "set to x"; add the difference instead.

## Quick recap

- Prefix sums: fast queries, slow updates. Segment and Fenwick trees: both O(log n).
- Segment tree node = answer for a range; query: outside → 0, inside → stored value, else split.
- Update a leaf, then fix the sums on the way up.
- Fenwick: `T[i]` covers `i & −i` items; prefix uses `i −= i & −i`, add uses `i += i & −i`.
- Fenwick for sums, segment tree for min/max and other operations.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-segment-tree-fenwick-tree