---
title: "Fenwick tree / segment tree"
url: https://algopath.pro/patterns/fenwick-segment-tree
language: en
summary: "A tree built over the ranges answers a query and accepts an update, both in log n. Prefix sums cannot do the second one."
updated: 2026-08-24
---

# Fenwick tree / segment tree

A tree built over the ranges answers a query and accepts an update, both in log n. Prefix sums cannot do the second one.

## How does Fenwick tree / segment tree work?

Each node of the tree owns a range and stores its answer. The root owns the whole array.

A node's answer is built from its two children. The combining rule is sum, min, max or something similar.

A query splits the wanted range against the tree. It stops at any node that lies fully inside.

At most two nodes per level are ever needed. That gives log n work per query.

An update changes one leaf and walks back to the root. Only the nodes above that leaf change.

A Fenwick tree does the same for prefix sums with far less code. A segment tree also handles min, max and lazy updates.

- `leaves: 3, 1, 4, 1` The array is [3, 1, 4, 1]. Each leaf owns one position.
- `level above: 4 and 5` Each node sums its own two children.
- `root = 9` The root holds the total of the whole array.
- `query 1 to 2` The wanted range is 1 plus 4. Two nodes cover it exactly.
- `set index 1 to 6` One leaf and two nodes above it change. The root becomes 14.

## When should you use Fenwick tree / segment tree?

- range sum or query with point updates interleaved
- live leaderboard or running rank while scores change
- count inversions or how many earlier values are larger
- range queries while the data keeps changing

## What is Fenwick tree / segment tree confused with?

- **Prefix sums** - Prefix sums read faster but break on any change. This pays log n to allow updates.
- **Difference array** - That takes many range updates and one read at the end. Here reads and writes are mixed.
- **Sweep line (event counting)** - A sweep processes events in sorted order and never looks back. Here queries arrive in any order.
- **Binary search (array)** - Both halve a range each step. One hunts a value, this one aggregates over a range.

## What is the time and space complexity of Fenwick tree / segment tree?

n up to 1e6 with q mixed operations gives O((n + q) log n). Memory is O(n) for a Fenwick tree.

## A worked example of Fenwick tree / segment tree

### Count the smaller values to the right

For every element, count how many later elements are smaller than it.

A nested loop is O(n squared) and dies at 1e5 elements.

Walk the array from the right, keeping a Fenwick tree over the values.

For each element, ask how many smaller values are recorded already. Then record this one.

```javascript
function countSmaller(nums) {
    const sorted = [...new Set(nums)].sort((a, b) => a - b);
    const rank = new Map(sorted.map((v, i) => [v, i + 1])); // ranks start at 1

    const tree = new Array(sorted.length + 1).fill(0);

    const add = (i) => {
        for (; i < tree.length; i += i & -i) tree[i]++;
    };

    const countBelow = (i) => {
        let total = 0;
        for (; i > 0; i -= i & -i) total += tree[i];
        return total;
    };

    const answer = new Array(nums.length);
    for (let i = nums.length - 1; i >= 0; i--) {
        const r = rank.get(nums[i]);
        answer[i] = countBelow(r - 1); // strictly smaller values already seen
        add(r);
    }

    return answer;
}
```

## Common mistakes with Fenwick tree / segment tree

- **Indexing a Fenwick tree from zero** The low-bit step needs indices to start at one. A zero index loops forever.
- **Using it where nothing ever changes** A prefix array answers in O(1) and costs nothing to read. Pay for a tree only when updates arrive.
- **Forgetting to compress the values** A tree sized by the value range dies on values up to 1e9. Map them to ranks first.
- **Combining ranges with a rule that does not fit** Sum and min work because order does not matter to them. An order-dependent rule needs more per node.

## Which interview problems use Fenwick tree / segment tree?

- **Range sum query mutable** Reads and writes mixed together in any order.
- **Count of smaller numbers after self** A Fenwick tree over compressed ranks.
- **Count of range sum** Prefix sums fed into the tree.
- **Reverse pairs** Merge sort or a Fenwick tree, either works.
- **Range minimum query** A segment tree, since min has no inverse.
- **Range sum query 2D mutable** A tree whose nodes are themselves trees.
- **My calendar II** A segment tree with lazy range updates.

## JavaScript

```javascript
class Fenwick {
    constructor(n) { this.tree = new Array(n + 1).fill(0); }
    update(i, delta) {
        for (; i < this.tree.length; i += i & -i) this.tree[i] += delta;
    }
    query(i) {
        let sum = 0;
        for (; i > 0; i -= i & -i) sum += this.tree[i];
        return sum;
    }
}
```

## Python

```python
class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total
```

## PHP

```php
class Fenwick {
    private array $tree;
    public function __construct(int $n) { $this->tree = array_fill(0, $n + 1, 0); }
    public function update(int $i, int $delta): void {
        for (; $i < count($this->tree); $i += $i & -$i) $this->tree[$i] += $delta;
    }
    public function query(int $i): int {
        $sum = 0;
        for (; $i > 0; $i -= $i & -$i) $sum += $this->tree[$i];
        return $sum;
    }
}
```