Segment Tree & Fenwick Tree

Answer range queries and change elements in O(log n) each: the segment tree for any combinable operation, lazy propagation for range updates, and the smaller Fenwick tree for prefix sums.

Overview

The problem it solves

You have an array and two kinds of requests arrive in any order: change one element, and ask for the sum (or the minimum, or the maximum) of a range. A plain array makes changes free and queries slow. A prefix-sum array makes queries free and changes slow, because every prefix after the change must be rebuilt. A segment tree makes both cost O(log n).

plain array — O(1) — O(n) — none
prefix sums — O(n) — O(1) — O(n)
segment tree — O(log n) — O(log n) — O(n)
Fenwick tree — O(log n) — O(log n) — O(n)

The trick is to store answers for ranges of many sizes ahead of time, so any query range can be assembled from a few stored pieces, and any change touches only the pieces that contain it.

The tree

Split the whole array in half, then each half in half, until each piece is one element. Every piece is a node that stores the sum of its range. The root covers everything, and the leaves are the elements. For [2, 5, 1, 4, 3, 7] the tree looks like this.

The tree lives in an array. The root is index 1, and the children of node i are 2i and 2i + 1. A node that covers l..r splits at mid = (l + r) // 2: the left child covers l..mid and the right child mid + 1..r.

1 — 0..5 — 22
2 — 0..2 — 8
3 — 3..5 — 14
4 — 0..1 — 7
5 — 2..2 — 1
6 — 3..4 — 7
7 — 5..5 — 7
8, 9 — 0..0, 1..1 — 2, 5
12, 13 — 3..3, 4..4 — 4, 3

Building is one pass over the tree: fill each leaf from the array, then each parent from its children. That is O(n) work, since there are fewer than 2n nodes.

A range query

To sum 1..4, start at the root and compare each node's range with the query range. There are three cases.

1 — 0..5 — partly — left + right
2 — 0..2 — partly — left + right
4 — 0..1 — partly — left + right
8 — 0..0 — outside — 0
9 — 1..1 — inside — 5
5 — 2..2 — inside — 1
3 — 3..5 — partly — left + right
6 — 3..4 — inside — 7
7 — 5..5 — outside — 0

The answer is 5 + 1 + 7 = 13. Nine nodes were visited and three supplied values. A query range never needs more than two fully covered nodes per level, and it visits at most about four nodes per level, so the visit count is O(log n). For a minimum query the identity is infinity and the combine step is min; any operation that can be combined from two halves works.

A point update

To set index 2 to 6, walk from the root to that leaf, change the leaf, and recompute the sum of every node on the way back up.

5 — 2..2 — 1 — 6
2 — 0..2 — 8 — 13
1 — 0..5 — 22 — 27

Only the ancestors of the leaf change, one per level, so an update is O(log n). The rest of the tree stays valid.

How big the array must be

With the root at index 1 and children at 2i and 2i + 1, the highest index used depends on n in an uneven way, because a range of odd length splits unevenly and the tree is not complete.

6 — 13 — 12 — 24
7 — 13 — 14 — 28
8 — 15 — 16 — 32
10 — 25 — 20 — 40
12 — 29 — 24 — 48

For n = 6 the index 13 is already above 2n, and for n = 10 the index 25 is above 2n as well. An array of 4n always fits, which is why that size is the convention. A bottom-up version, which stores the leaves at indexes n..2n - 1 and the parent of i at i // 2, needs exactly 2n slots and is the shortest to code. The JavaScript example below uses it.

Lazy propagation for range updates

Add 3 to every element in 1..4. Updating five leaves one at a time costs five O(log n) walks, and a range of length n would cost O(n log n). Lazy propagation keeps the update at the highest nodes that the range fully covers and records the pending amount there, so children are fixed only when a later query or update actually needs to look inside them.

1 — 0..5 — partly — push pending down (none), recurse
2 — 0..2 — partly — push pending down (none), recurse
4 — 0..1 — partly — push pending down (none), recurse
8 — 0..0 — outside — nothing
9 — 1..1 — inside — sum += 3 × 1
5 — 2..2 — inside — sum += 3 × 1
3 — 3..5 — partly — push pending down (none), recurse
6 — 3..4 — inside — sum += 3 × 2, pending = 3
7 — 5..5 — outside — nothing

Node 6 now says 13 and carries a pending 3. Its children 12 and 13 still say 4 and 3, which is stale but harmless: nobody reads them without first passing through node 6, and passing through a partly covered node pushes its pending amount down. A later query for 3..3 visits node 6, pushes the 3 into both children (12 becomes 7, 13 becomes 6), and returns 7. Each range update and each query still visits O(log n) nodes.

> [!IMPORTANT] > Push the pending value down before recursing into either child, on updates as well as queries. Forgetting it on one path is the classic lazy-propagation bug, and it shows up only on inputs that touch the same range twice.

The Fenwick tree

A Fenwick tree, also called a binary indexed tree, is a smaller structure for the special case where the query is a prefix sum and the update adds to one element. It is one array of size n + 1, indexed from 1. Slot i stores the sum of a block that ends at i and has length equal to the lowest set bit of i, written i & -i.

1 — 0001 — 1 — 1..1 — 2 — 0
2 — 0010 — 2 — 1..2 — 4 — 0
3 — 0011 — 1 — 3..3 — 4 — 2
4 — 0100 — 4 — 1..4 — 8 — 0
5 — 0101 — 1 — 5..5 — 6 — 4
6 — 0110 — 2 — 5..6 — 8 — 4
7 — 0111 — 1 — 7..7 — 8 — 6
8 — 1000 — 8 — 1..8 — 16 — 0

A prefix query starts at i and repeatedly removes the lowest set bit, adding each slot it lands on; that is at most one step per bit, so O(log n). An update starts at i and repeatedly adds the lowest set bit, adjusting every slot whose block contains i. For [2, 5, 1, 4, 3, 7] the slots are [2, 7, 1, 12, 3, 10], and the prefix sum through 1-based position 5 is slot 5 plus slot 4, which is 3 + 12 = 15. A range sum is the difference of two prefix sums.

prefix sums, point add — yes, less code, n + 1 slots against 2n to 4n — yes
range sum, point set — yes, add the difference — yes
range minimum — no, min cannot be subtracted — yes
range add, range sum — only with two trees and a trick — yes, with lazy propagation
any combinable operation — no — yes

The Fenwick tree needs an operation with an inverse, because a range answer is the difference of two prefixes. Sums have one; minimum and maximum do not.

A tree over values, not positions

Count of Smaller Numbers After Self asks, for each element, how many elements to its right are smaller. Index the tree by value instead of by position: walk the array from right to left, ask how many values below the current one have been inserted so far, then insert the current value. With values up to 10⁹ but only n of them, first replace each value by its rank among the distinct values (coordinate compression) so the tree has n slots.

1 — 1 — 0 — 1, 1, 0, 1
6 — 4 — 1 — 1, 1, 0, 2
2 — 2 — 1 — 1, 2, 0, 3
5 — 3 — 2 — 1, 2, 1, 4

For [5, 2, 6, 1] the answer, read back in array order, is [2, 1, 1, 0]. The same idea counts inversions and answers order-statistic questions in O(n log n).

How to spot it

range queries and single-element changes, many of both — segment tree, or Fenwick if it is sums
add a value to a whole range, then query ranges — segment tree with lazy propagation
how many earlier or later elements are smaller — Fenwick over compressed values
range queries but the array never changes — prefix sums, or a sparse table for min and max; a tree is more than you need
only a few queries — just scan; O(n) per query is fine

What you will be able to do

Draw the tree for a small array and read off which nodes a query touches.
Write build, point update and range query, and explain why each is O(n) or O(log n).
Say why the array is 4n and how the bottom-up version gets away with 2n.
Add lazy propagation for range updates and name the bug it invites.
Choose between a Fenwick tree and a segment tree, and count smaller elements with a tree over values.

When to use it

Sum, minimum or maximum of a range while single elements keep changing
Adding a value to every element in a range, mixed with range queries (lazy propagation)
Counting how many earlier or later elements are smaller or larger (a tree over values)
Counting inversions or answering order-statistic questions in O(n log n)
Sweep-line problems where the set of active intervals changes and you need a range maximum
Any array where both queries and updates on ranges must run in O(log n)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio