---
title: Fenwick & Segment Trees
module: Data Structures
moduleNumber: 4
lessonNumber: 7
order: 407
summary: |
  A prefix-sum array answers a range sum in $O(1)$ but pays $O(n)$ per update;
  a plain array updates in $O(1)$ but pays $O(n)$ per range sum. Fenwick and
  segment trees give us _both_ in $O(\log n)$. The Fenwick (binary indexed) tree
  is a tiny array keyed by the low bit; the segment tree is a general balanced
  tree over canonical ranges that handles any associative aggregate and, with
  lazy propagation, range updates too.
topics: [Range Queries]
sources:
  - book: CLRS
    ref: "Ch. 14 — Augmenting Data Structures"
  - book: Skiena
    ref: "§3.x — Range Queries / Augmented Structures"
  - book: Erickson
    ref: "Ch. — Data Structures"
practice:
  - title: 'Range Sum Query - Mutable'
    slug: range-sum-query-mutable
    difficulty: Medium
  - title: 'Count of Smaller Numbers After Self'
    slug: count-of-smaller-numbers-after-self
    difficulty: Hard
  - title: 'Range Sum Query 2D - Mutable'
    slug: range-sum-query-2d-mutable
    difficulty: Hard
  - title: 'The Skyline Problem'
    slug: the-skyline-problem
    difficulty: Hard
---

We have an array $A[1\dots n]$ and two operations we want to interleave freely:
**update** a single entry, and ask for the **sum of a contiguous range** $A[l\dots r]$.
The two obvious data structures each ace one operation and fail the other. Keep
$A$ as is and an update is a single write in $O(1)$, but a range sum scans the
range in $\Theta(n)$. Precompute a [**prefix-sum array**](/algorithms/sequences/prefix-sums) $P[i] = A[1] + \dots + A[i]$
and a range sum collapses to $P[r] - P[l-1]$ in $O(1)$, but now a single update
to $A[k]$ disturbs every $P[i]$ with $i \ge k$, an $\Theta(n)$ repair. We want a
structure that splits the difference and does _both_ in $O(\log n)$.

$$
% caption: The tradeoff that motivates these structures. A range sum on a plain array must
%          scan the whole range, $\Theta(n)$ (top). A prefix-sum array answers that sum as
%          one subtraction $P[r]-P[l-1]$, but a single update to $A[k]$ then dirties every
%          later prefix $P[k\dots n]$, $\Theta(n)$ to repair (bottom). Each structure is
%          $O(1)$ on one operation and $\Theta(n)$ on the other.
\begin{tikzpicture}[
  cell/.style={draw, minimum width=7mm, minimum height=7mm, inner sep=0, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % --- plain array: range sum scans ---
  \node[font=\footnotesize, anchor=east] at (-0.3,0) {$A$};
  \foreach \i [count=\c from 0] in {3,1,4,1,5,9,2,6} {
    \node[cell] (a\c) at (\c*0.78,0) {$\i$};
  }
  \draw[black, thick] (a2.south west) ++(0,-0.12) -- ++(0,-0.22) -- ++(3*0.78,0) -- ++(0,0.22);
  \node[draw=none, font=\scriptsize, black] at (3.3*0.78,-0.95) {range sum: scan the range};
  % --- prefix array: update ripples ---
  \begin{scope}[yshift=-2.9cm]
    \node[font=\footnotesize, anchor=east] at (-0.3,0) {$P$};
    \foreach \i [count=\c from 0] in {3,4,8,9,14,23,25,31} {
      \ifnum\c>2 \node[cell, fill=black!12] (p\c) at (\c*0.78,0) {$\i$};
      \else \node[cell] (p\c) at (\c*0.78,0) {$\i$}; \fi
    }
    \node[draw=acc, very thick, minimum width=7mm, minimum height=7mm, inner sep=0] at (3*0.78,0) {};
    \node[draw=none, font=\footnotesize, acc] at (3*0.78,0.75) {\texttt{update} $A[4]$};
    \draw[->, acc] (3*0.78,0.5) -- (p3.north);
    \node[draw=none, font=\scriptsize, black] at (5.3*0.78,-0.7) {ripples through P[4..8]};
  \end{scope}
\end{tikzpicture}
$$

The idea, in the spirit of the previous lessons on augmenting trees with
subtree summaries,[^clrs-augment] is to store **partial sums over blocks** so that any prefix is
the sum of a few blocks and any single element lives in only a few blocks. Two
classic structures realize this: the **Fenwick tree**, which is
compact and exploits the binary representation of the index, and the **segment
tree**, which is more general and handles any associative aggregate plus range
updates.

## Fenwick trees: indexing by the low bit

A **Fenwick tree** (or **binary indexed tree**) is a 1-indexed array $F[1\dots n]$
where $F[i]$ stores the sum of a contiguous block of $A$ _ending at_ index $i$.
The length of that block is $\lowbit(i)$, the value of the lowest
set bit of $i$:

$$
\lowbit(i) = i \mathbin{\&} (-i), \qquad
F[i] = \sum_{j \,=\, i - \lowbit(i) + 1}^{i} A[j].
$$

That is, $F[i]$ covers the half-open range $\parens{\,i - \lowbit(i),\ i\,}$.
This relies on two's-complement arithmetic: $-i$ is _flip every bit of $i$,
then add one_. Trace it for $i = 12$ in five bits:

$$
\begin{aligned}
i &= 12 &&= (01100)_2 \\
\text{flip} &&&= (10011)_2 \\
\text{add } 1 \;\Rightarrow\; -i &= -12 &&= (10100)_2 \\
i \mathbin{\&} (-i) &= 4 &&= (00100)_2.
\end{aligned}
$$

Why does this always isolate the lowest set bit? Write $i$ as some prefix of
bits, then the lowest $1$, then a run of trailing zeros: $i = (\,x\,1\,
\underbrace{0\cdots0}_{t}\,)_2$. Flipping gives $(\,\bar{x}\,0\,1\cdots1\,)_2$,
and adding $1$ carries through the trailing ones and stops at the flipped $0$:
$-i = (\,\bar{x}\,1\,0\cdots0\,)_2$. Below the lowest set bit both numbers are
all zeros; _at_ it both have a $1$; above it every bit of $-i$ is the complement
of the corresponding bit of $i$. The AND therefore keeps exactly one bit — the
lowest set bit. Concretely: $\lowbit(6) = 2$ since
$6 = (110)_2$, so $F[6]$ covers indices $5\dots 6$; $\lowbit(8) =
8$ since $8 = (1000)_2$, so $F[8]$ covers the whole prefix $1\dots 8$; and
$\lowbit(i) = 1$ for every odd $i$, so odd entries cover just
themselves.

Here is the whole structure for the running array $A = [3,1,4,1,5,9,2,6]$. Each
bracket is one Fenwick entry, storing the sum of the cells it spans:

$$
% caption: The Fenwick tree for $A = [3,1,4,1,5,9,2,6]$. Each $F[i]$ covers the block of
%          length $\lowbit(i)$ ending at $i$ and stores that block's sum:
%          the odd entries store single cells, $F[2]$ and $F[6]$ store pairs, $F[4]$ stores
%          the sum of $A[1\dots4]$, and $F[8]$ stores the total. Every index is covered by
%          exactly one bracket per "level," and each level halves the number of brackets.
\begin{tikzpicture}[
  cell/.style={draw, minimum width=9mm, minimum height=8mm, inner sep=0, font=\small},
  rng/.style={font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % the array A[1..8] with index labels above
  \foreach \i [count=\c from 1] in {3,1,4,1,5,9,2,6} {
    \node[cell] (a\c) at (\c*0.95, 0) {$\i$};
    \node[font=\scriptsize, black] at (\c*0.95, 0.68) {\c};
  }
  \node[rng] at (-0.4, 0) {$A$};
  % F[i] coverage brackets below, one row per "level" of lowbit
  % length-1 blocks: F[1]=3, F[3]=4, F[5]=5, F[7]=2
  \foreach \i/\v in {1/3, 3/4, 5/5, 7/2} {
    \draw (a\i.south west) ++(0.1,-0.15) -- ++(0,-0.18) -- ++(0.75,0) -- ++(0,0.18);
    \node[rng] at (\i*0.95, -0.98) {$F[\i]$ = \v};
  }
  % length-2 blocks: F[2]=4 covers 1..2, F[6]=14 covers 5..6
  \draw (a1.south west) ++(0.1,-1.05) -- ++(0,-0.18) -- ++(1.7,0) -- ++(0,0.18);
  \node[rng] at (1.42, -1.88) {$F[2]$ = 4};
  \draw (a5.south west) ++(0.1,-1.05) -- ++(0,-0.18) -- ++(1.7,0) -- ++(0,0.18);
  \node[rng] at (5.22, -1.88) {$F[6]$ = 14};
  % length-4 block: F[4]=9 covers 1..4
  \draw (a1.south west) ++(0.1,-1.95) -- ++(0,-0.18) -- ++(3.6,0) -- ++(0,0.18);
  \node[rng] at (2.37, -2.78) {$F[4]$ = 9};
  % length-8 block: F[8]=31 covers 1..8  (accent)
  \draw[acc, thick] (a1.south west) ++(0.1,-2.85) -- ++(0,-0.18) -- ++(7.4,0) -- ++(0,0.18);
  \node[rng, acc] at (4.27, -3.68) {$F[8]$ = 31 covers A[1..8]};
\end{tikzpicture}
$$

Reading the brackets off into an array: $F = [3,\,4,\,4,\,9,\,5,\,14,\,2,\,31]$.
The entry $F[6] = A[5] + A[6] = 5 + 9 = 14$; the entry $F[4] = A[1] + \dots +
A[4] = 9$. Nothing else is stored — the structure _is_ this one array.

**Prefix sum.** To compute $P[i] = A[1] + \dots + A[i]$ we peel off blocks from
the right. $F[i]$ accounts for the topmost block ending at $i$; the rest of the
prefix ends at $i - \lowbit(i)$, so we jump there and repeat,
clearing one set bit each step until we reach $0$.

```algorithm
caption: $\textsc{PrefixSum}(F, i)$ — return $A[1] + \dots + A[i]$
$s \gets 0$
while $i > 0$ do
  $s \gets s + F[i]$
  $i \gets i - \lowbit(i)$ // clear the lowest set bit
return $s$
```

Trace it on the running array, $F = [3,4,4,9,5,14,2,31]$, for
$\textsc{PrefixSum}(7)$:

| step | $i$ (binary) | read | running $s$ | next $i = i - \lowbit(i)$ |
| --- | --- | --- | --- | --- |
| 1 | $7 = (111)_2$ | $F[7] = 2$ | $2$ | $7 - 1 = 6$ |
| 2 | $6 = (110)_2$ | $F[6] = 14$ | $16$ | $6 - 2 = 4$ |
| 3 | $4 = (100)_2$ | $F[4] = 9$ | $25$ | $4 - 4 = 0$ |

The loop stops at $i = 0$ and returns $25$; a direct check gives $3+1+4+1+5+9+2
= 25$. Each subtraction clears the lowest set bit of $i$ — $(111)_2 \to (110)_2
\to (100)_2 \to 0$ — and each cleared bit contributed one block: $F[7]$ covers
$A[7]$, $F[6]$ covers $A[5\dots6]$, $F[4]$ covers $A[1\dots4]$. The three
blocks tile $A[1\dots7]$ with no gaps and no overlaps.

That tiling is not an accident of $i = 7$. The binary expansion of any index is
a sum of powers of two, and the walk peels those powers off from the smallest
up. For a larger index like $i = 13 = 8 + 4 + 1 = (1101)_2$, the visit sequence
is $13 \to 12 \to 8 \to 0$:

$$
% caption: $\textsc{PrefixSum}(13)$ follows the set bits of $13 = (1101)_2$. The walk
%          $13 \to 12 \to 8 \to 0$ reads three entries whose blocks — $F[13]$ of length
%          $1$, $F[12]$ of length $4$, $F[8]$ of length $8$ — tile the prefix $A[1\dots13]$
%          exactly. One block per set bit, so at most $\lfloor \log_2 n \rfloor + 1$ reads.
\begin{tikzpicture}[
  cell/.style={draw, minimum width=6.4mm, minimum height=6.4mm, inner sep=0, font=\footnotesize},
  rng/.style={font=\footnotesize},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % index cells 1..13, visited entries accented
  \foreach \i in {1,...,13} {
    \node[cell] (c\i) at (\i*0.68, 0) {$\i$};
  }
  \foreach \i in {8,12,13} {
    \node[draw=acc, very thick, minimum width=6.4mm, minimum height=6.4mm, inner sep=0] at (\i*0.68,0) {};
  }
  % hop arrows above: 13 -> 12 -> 8 -> 0
  \draw[acc, thick, ->] (c13.north) ++(0,0.05) to[bend right=50] ($(c12.north)+(0,0.05)$);
  \draw[acc, thick, ->] (c12.north) ++(0,0.05) to[bend right=40] ($(c8.north)+(0,0.05)$);
  \draw[acc, thick, ->] (c8.north) ++(0,0.05) to[bend right=30] ($(c1.north)+(-0.7,0.05)$);
  \node[rng, acc] at (0.0, 0.30) {0};
  % coverage brackets below
  \draw[acc, thick] (c1.south west) ++(0.06,-0.15) -- ++(0,-0.18) -- ++(5.32,0) -- ++(0,0.18);
  \node[rng] at (3.06, -0.95) {$F[8]$: length 8};
  \draw[acc, thick] (c9.south west) ++(0.06,-0.15) -- ++(0,-0.18) -- ++(2.6,0) -- ++(0,0.18);
  \node[rng] at (7.14, -0.95) {$F[12]$: length 4};
  \draw[acc, thick] (c13.south west) ++(0.06,-0.15) -- ++(0,-0.18) -- ++(0.56,0) -- ++(0,0.18);
  \node[rng] at (8.84, -0.95) {$F[13]$};
\end{tikzpicture}
$$

**Point update.** When $A[k]$ changes by $\delta$, every $F[i]$ whose block
_contains_ $k$ must change by $\delta$. Repeatedly _adding_ the low bit visits
those indices and no others: starting at $k$, each step $i \gets i +
\lowbit(i)$ moves to the next larger block that covers $k$, until we
run past $n$.

```algorithm
caption: $\textsc{Update}(F, k, \delta)$ — add $\delta$ to $A[k]$
while $k \le n$ do
  $F[k] \gets F[k] + \delta$
  $k \gets k + \lowbit(k)$ // move to the next covering block
```

Trace $\textsc{Update}(5, +2)$ — add $2$ to $A[5]$ — on the running array:

| step | $k$ (binary) | write | next $k = k + \lowbit(k)$ |
| --- | --- | --- | --- |
| 1 | $5 = (101)_2$ | $F[5] \gets 5 + 2 = 7$ | $5 + 1 = 6$ |
| 2 | $6 = (110)_2$ | $F[6] \gets 14 + 2 = 16$ | $6 + 2 = 8$ |
| 3 | $8 = (1000)_2$ | $F[8] \gets 31 + 2 = 33$ | $8 + 8 = 16 > n$, stop |

Exactly the right entries changed: $F[5]$ covers $A[5]$ alone, $F[6]$ covers
$A[5\dots6]$, and $F[8]$ covers $A[1\dots8]$ — every block that contains index
$5$, and no other. $F[7]$ covers only $A[7]$, so the walk correctly skips it.
A follow-up $\textsc{PrefixSum}(7)$ now reads $F[7] + F[6] + F[4] = 2 + 16 + 9
= 27 = 25 + 2$, as it must.

> **Lemma (update correctness).** $F[j]$'s block contains index $k$ if and only
> if $j$ appears in the sequence $k,\ k + \lowbit(k),\ \dots$
> generated by $\textsc{Update}(k)$.
>

> **Proof.** $F[j]$ covers $(\,j - \lowbit(j),\ j\,]$, so it
> contains $k$ iff $j \ge k$ and $j - \lowbit(j) < k$. The smallest
> such $j$ is $k$ itself. Suppose $j$ covers $k$ and write $2^a =
> \lowbit(j)$; we show the next covering index is exactly $j + 2^a$.
> First, $j + 2^a$ covers $k$: adding $2^a$ clears bit $a$ and carries upward, so
> $\lowbit(j + 2^a) \ge 2^{a+1}$, hence $(j + 2^a) -
> \lowbit(j + 2^a) \le j - 2^a < k$. Second, nothing strictly
> between covers $k$: any $j' = j + s$ with $0 < s < 2^a$ has
> $\lowbit(j') = \lowbit(s)$, because the bits of $j$
> below position $a$ are all zero; then $j' - \lowbit(j') = j + s -
> \lowbit(s) \ge j \ge k$, so its block starts at or after $k$ and
> misses it. Induction gives exactly the $+\lowbit$ chain. $\qed$

> **Lemma.** Both $\textsc{PrefixSum}$ and $\textsc{Update}$ touch $O(\log n)$
> entries of $F$.
>

> **Proof.** $\textsc{PrefixSum}$ clears one set bit of $i$ per iteration, so it
> runs at most as many times as $i$ has set bits, at most $\lfloor \log_2 n
> \rfloor + 1$. For $\textsc{Update}$, adding $\lowbit(k)$ to $k$
> carries the lowest set bit upward and strictly increases the _value_ of the low
> bit each step (a $1$-run is replaced by a higher single $1$), so it too runs
> $O(\log n)$ times before exceeding $n$. $\qed$

The two walks are mirror images on the same number line. $\textsc{Update}$ climbs
to larger indices by _adding_ the low bit, visiting every block that owns the
changed element; $\textsc{PrefixSum}$ descends to smaller indices by _subtracting_
it, peeling off the blocks that tile the prefix. The same $\lowbit$
hop drives both, in opposite directions.

$$
% caption: The lowbit duality on $F[1\dots8]$. $\textsc{Update}(5)$ climbs $5 \to 6 \to 8$
%          by adding the low bit (top, accent); $\textsc{PrefixSum}(7)$ descends
%          $7 \to 6 \to 4 \to 0$ by clearing it (bottom, grey). Both walks ride the same
%          hop in opposite directions.
\begin{tikzpicture}[
  cell/.style={draw, minimum width=8mm, minimum height=8mm, inner sep=0, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % terminal cell 0 (dashed), then index cells 1..8
  \node[cell, dashed, black] (f0) at (0,0) {$0$};
  \foreach \i in {1,...,8} {
    \node[cell] (f\i) at (\i*0.95, 0) {$\i$};
  }
  \node[font=\footnotesize] at (-0.75,0) {$F$};
  % --- Update(5): 5 -> 6 -> 8  (above, adding the low bit) ---
  \draw[acc, thick, ->] (f5.north) ++(0.06,0.05) to[bend left=48] ($(f6.north)+(-0.06,0.05)$);
  \draw[acc, thick, ->] (f6.north) ++(0.06,0.05) to[bend left=35] ($(f8.north)+(0,0.05)$);
  \node[acc, font=\scriptsize, anchor=east] at ($(f5.north)+(-0.1,0.28)$) {start};
  \node[acc, font=\footnotesize] at (4.3,1.30) {\texttt{Update(5)}: add the low bit};
  % --- PrefixSum(7): 7 -> 6 -> 4 -> 0 (below, clearing the low bit) ---
  \draw[black, thick, ->] (f7.south) ++(-0.06,-0.05) to[bend left=48] ($(f6.south)+(0.06,-0.05)$);
  \draw[black, thick, ->] (f6.south) ++(-0.06,-0.05) to[bend left=40] ($(f4.south)+(0.06,-0.05)$);
  \draw[black, thick, ->] (f4.south) ++(-0.06,-0.05) to[bend left=32] ($(f0.south)+(0.06,-0.05)$);
  \node[black, font=\scriptsize, anchor=west] at ($(f7.south)+(0.1,-0.28)$) {start};
  \node[black, font=\footnotesize] at (4.3,-1.42) {\texttt{PrefixSum(7)}: clear the low bit};
\end{tikzpicture}
$$

A range sum is then two prefix queries:

$$
\textsc{RangeSum}(l, r) = \textsc{PrefixSum}(r) - \textsc{PrefixSum}(l - 1),
$$

so both update and range sum cost $O(\log n)$, with $F$ occupying a single array
of $n$ words and no pointers.[^skiena-fenwick] Building $F$ takes $O(n)$ by a
linear in-place pass described below, rather than $n$ separate updates.

> **Intuition.** Read the binary expansion of $i$ as a sum of powers of two; each
> set bit names one Fenwick block, and the blocks tile the prefix $1\dots i$
> exactly. Walking down clears bits to _read_ a prefix; walking up sets the carry
> to _patch_ every block that owns a given element.

### The implicit tree

The array $F$ is a flattened forest, and seeing the tree explains both
walks. Define $\parent(i) = i + \lowbit(i)$. Under
this map every index at most $n$ hangs below a power of two, and each node's
block is the disjoint union of its own array cell and its children's blocks:

$$
F[i] \;=\; A[i] \;+ \sum_{\substack{c \,:\, \parent(c) = i}} F[c].
$$

Check it at $i = 8$: the children of $8$ are $7$ (since $7 + 1 = 8$), $6$
(since $6 + 2 = 8$), and $4$ (since $4 + 4 = 8$), and indeed

$$
F[8] = A[8] + F[7] + F[6] + F[4] = 6 + 2 + 14 + 9 = 31.
$$

The two operations are just the two natural walks in this forest.
$\textsc{Update}(k)$ follows parent pointers from $k$ toward the root — the
leaf-to-root path — which, by the correctness lemma, is the set of blocks
containing $k$. $\textsc{PrefixSum}(i)$ hops across the forest from one
subtree root to the next one on its left; each hop $i \gets i -
\lowbit(i)$ discards a fully-counted subtree. Since
$\parent(i)$ always has a strictly larger low bit, no root-ward
path is longer than the number of bit positions, $\lfloor \log_2 n \rfloor + 1$
— the tree is implicitly balanced, with no rotations, no pointers, and no
bookkeeping beyond the index arithmetic itself.

The parent map also gives the $O(n)$ construction promised above in one
left-to-right pass: initialize $F \gets A$, then for $i = 1, \dots, n$ add
$F[i]$ into $F[i + \lowbit(i)]$ if that parent exists. By the time
the loop reaches $i$, every descendant of $i$ has already deposited its sum, so
each entry is finished exactly when it is passed along — $n$ additions total,
versus $\Theta(n \log n)$ for $n$ separate calls to $\textsc{Update}$.

The one catch: this works because sums are **invertible** — we recover $A[l\dots r]$
by subtracting two prefixes. For non-invertible aggregates like $\min$ or
$\max$, $P[r] - P[l-1]$ is meaningless, and we need a structure that queries an
_arbitrary_ range directly. That is the segment tree.

::impl{algo="fenwick,fenwick_2d"}

## Segment trees: a balanced tree of canonical ranges

A **segment tree** over $A[0\dots n-1]$ is a balanced binary tree whose **leaves**
are the array entries and whose every **internal node stores the aggregate of the
contiguous range its subtree spans**. The root covers $[0, n-1]$; a node covering
$[lo, hi]$ with $lo < hi$ splits at $mid = \lfloor (lo+hi)/2 \rfloor$ into children
covering $[lo, mid]$ and $[mid+1, hi]$. The stored aggregate can be sum, $\min$,
$\max$, or $\gcd$: **any associative operation** (formally, any monoid), since a
node's value is its two children's values combined.

$$
% caption: A segment tree over 8 elements; the $O(\log n)$ canonical nodes covering
%          $[1,5]$ are highlighted
\begin{tikzpicture}[
  every node/.style={draw, minimum width=11mm, minimum height=6mm, inner sep=1pt, font=\footnotesize},
  level 1/.style={sibling distance=56mm},
  level 2/.style={sibling distance=28mm},
  level 3/.style={sibling distance=14mm},
  level distance=12mm,
  edge from parent/.style={draw, -}]
  \definecolor{acc}{HTML}{2348F2}
  \node {[0,7]}
    child {node {[0,3]}
      child {node {[0,1]}
        child {node {[0,0]}}
        child {node[draw=acc, very thick, fill=acc!15] {[1,1]}}
      }
      child {node[draw=acc, very thick, fill=acc!15] {[2,3]}
        child {node {[2,2]}}
        child {node {[3,3]}}
      }
    }
    child {node {[4,7]}
      child {node[draw=acc, very thick, fill=acc!15] {[4,5]}
        child {node {[4,4]}}
        child {node {[5,5]}}
      }
      child {node {[6,7]}
        child {node {[6,6]}}
        child {node {[7,7]}}
      }
    };
\end{tikzpicture}
$$

**Query.** To aggregate $A[l\dots r]$ we descend from the root. At a node covering
$[lo, hi]$: if $[lo,hi]$ lies entirely inside $[l,r]$ we return its stored value
without recursing (a **canonical** node); if it is disjoint from $[l,r]$ we return
the monoid identity; otherwise we recurse into both children and combine. The
query range $[l, r]$ decomposes into $O(\log n)$ canonical nodes, at most two per
level of the tree, so a range query costs $O(\log n)$. In the figure, $[1,5]$ is
covered by the three shaded nodes $[1,1]$, $[2,3]$, $[4,5]$, and their union is
exactly $\{1,2,3,4,5\}$.

> **Lemma.** Any range $[l,r]$ is covered by at most $2$ canonical nodes per level,
> hence $O(\log n)$ in total.
>

> **Proof sketch.** On each level the nodes partition $[0,n-1]$ into equal blocks.
> The recursion only branches at nodes that _straddle_ an endpoint of $[l,r]$;
> at most one node per level straddles $l$ and at most one straddles $r$, and
> every node strictly between them is returned whole without descending. With
> $O(\log n)$ levels that is $O(\log n)$ canonical pieces. $\qed$

### A worked query

Build the tree over the running array $A = [3,1,4,1,5,9,2,6]$ bottom-up: the
leaves take $A$'s values, and each internal node sums its children — $[0,1]
= 3 + 1 = 4$, $[2,3] = 4 + 1 = 5$, $[4,5] = 5 + 9 = 14$, $[6,7] = 2 + 6 = 8$,
then $[0,3] = 9$ and $[4,7] = 22$, and the root $[0,7] = 31$. Now run
$\textsc{Sum}(1, 5)$ and record every node the recursion touches:

| node | value | relation to $[1,5]$ | action |
| --- | --- | --- | --- |
| $[0,7]$ | $31$ | straddles | recurse into both children |
| $[0,3]$ | $9$ | straddles | recurse into both children |
| $[0,1]$ | $4$ | straddles | recurse into both children |
| $[0,0]$ | $3$ | disjoint | return $0$ |
| $[1,1]$ | $1$ | inside | **return $1$** (canonical) |
| $[2,3]$ | $5$ | inside | **return $5$** (canonical) |
| $[4,7]$ | $22$ | straddles | recurse into both children |
| $[4,5]$ | $14$ | inside | **return $14$** (canonical) |
| $[6,7]$ | $8$ | disjoint | return $0$ |

The answer is $1 + 5 + 14 = 20$, and directly: $A[1] + \dots + A[5] = 1 + 4 +
1 + 5 + 9 = 20$. The recursion visited $9$ of the tree's $15$ nodes; on a
larger tree the proportion collapses, since only the two root-to-endpoint paths
are ever explored.

$$
% caption: $\textsc{Sum}(1,5)$ on the tree for $A = [3,1,4,1,5,9,2,6]$, values shown.
%          Solid accent nodes are the canonical decomposition ($1 + 5 + 14 = 20$); dashed
%          accent nodes were visited but straddle or miss the range — the straddling ones
%          recurse, the disjoint ones ($3$ at index $0$, the $8$ covering $[6,7]$) return
%          the identity $0$. Plain nodes are never touched.
\begin{tikzpicture}[
  every node/.style={draw, minimum width=9mm, minimum height=6mm, inner sep=1pt, font=\footnotesize},
  level 1/.style={sibling distance=56mm},
  level 2/.style={sibling distance=28mm},
  level 3/.style={sibling distance=14mm},
  level distance=12mm,
  edge from parent/.style={draw, -}]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw=acc, dashed] {31}
    child {node[draw=acc, dashed] {9}
      child {node[draw=acc, dashed] {4}
        child {node[draw=acc, dashed] {3}}
        child {node[draw=acc, very thick, fill=acc!15] {1}}
      }
      child {node[draw=acc, very thick, fill=acc!15] {5}
        child {node {4}}
        child {node {1}}
      }
    }
    child {node[draw=acc, dashed] {22}
      child {node[draw=acc, very thick, fill=acc!15] {14}
        child {node {5}}
        child {node {9}}
      }
      child {node[draw=acc, dashed] {8}
        child {node {2}}
        child {node {6}}
      }
    };
  % leaf indices
  \foreach \x/\i in {-4.9/0, -3.5/1, -2.1/2, -0.7/3, 0.7/4, 2.1/5, 3.5/6, 4.9/7} {
    \node[draw=none, font=\scriptsize, black] at (\x, -4.1) {\i};
  }
\end{tikzpicture}
$$

**Point update.** To change $A[k]$, update the corresponding leaf and walk back up
to the root, recomputing each ancestor as the combination of its (now-updated)
children — one node per level, $O(\log n)$ work. Setting $A[5] \gets 11$ (it was
$9$) in the tree above rewrites exactly one root-to-leaf path: the leaf becomes
$11$, then $[4,5] = 5 + 11 = 16$, then $[4,7] = 16 + 8 = 24$, then the root
$[0,7] = 9 + 24 = 33$. Four writes, no other node consulted. Building the tree
bottom-up visits each of the $\Theta(n)$ nodes once, so construction is $O(n)$,
and the tree needs at most $2n$ (commonly allocated as $4n$) nodes, roughly $2$
to $4\times$ a Fenwick tree's memory.

::impl{algo="segment_tree"}

### Lazy propagation: range updates in $O(\log n)$

A point-update segment tree still pays $\Theta(n \log n)$ to add a value to a
_whole range_ element by element. **Lazy propagation** fixes this. When an update
applies to a range that exactly covers a node's interval, we apply it to that
node's aggregate and stash a **pending tag** on the node instead of recursing into
its children. The tag is **pushed down** to the children only later, lazily, when
a subsequent query or update actually needs to enter that subtree.

> **Intuition.** A node's tag records an update that everything below it still
> needs. The tag is applied just-in-time, the moment a query or update descends
> past the node — never sooner. Each range update touches the same $O(\log n)$
> canonical nodes a query does, tagging them in $O(1)$ each.

$$
% caption: Lazy push-down. A pending $+5$ tag on $[0,3]$ is applied to that node's
%          aggregate; only when a query descends does the tag flow to the children $[0,1]$
%          and $[2,3]$
\begin{tikzpicture}[
  every node/.style={draw, minimum width=13mm, minimum height=7mm, inner sep=1pt, font=\footnotesize},
  level 1/.style={sibling distance=24mm},
  level 2/.style={sibling distance=12mm},
  level distance=13mm,
  edge from parent/.style={draw, -}]
  \definecolor{acc}{HTML}{2348F2}
  % --- before push-down ---
  \begin{scope}
    \node[fill=acc!15, draw=acc, very thick] (n) {[0,3]: +5}
      child {node {[0,1]}}
      child {node {[2,3]}};
    \node[draw=none, font=\footnotesize, text=acc] at (1.9,0.1) {tag held};
  \end{scope}
  % transition arrow (ends well before the right subtree's left child)
  \draw[->, very thick] (3.1,-0.8) -- node[draw=none, above, font=\footnotesize] {descend} (4.3,-0.8);
  % --- after push-down ---
  \begin{scope}[xshift=68mm]
    \node (m) {[0,3]}
      child {node[fill=acc!15, draw=acc, very thick] {[0,1]: +5}}
      child {node[fill=acc!15, draw=acc, very thick] {[2,3]: +5}};
    \node[draw=none, font=\footnotesize, text=acc] at (0,-2.6) {tag pushed to children};
  \end{scope}
\end{tikzpicture}
$$

### A worked range update

Run $\textsc{RangeAdd}(0, 5, +5)$ on the original tree for $A =
[3,1,4,1,5,9,2,6]$. The range $[0,5]$ decomposes into the canonical nodes
$[0,3]$ and $[4,5]$ — the same decomposition a query would compute. At each
canonical node we apply the update to the stored sum in $O(1)$ (a $+5$ over a
node covering $\mathit{len}$ cells adds $5 \cdot \mathit{len}$) and record the
tag:

- $[0,3]$: sum $9 \gets 9 + 5 \cdot 4 = 29$, tag $\gets +5$;
- $[4,5]$: sum $14 \gets 14 + 5 \cdot 2 = 24$, tag $\gets +5$;
- on the way back up, recompute the ancestors: $[4,7] = 24 + 8 = 32$ and the
  root $[0,7] = 29 + 32 = 61$.

Six nodes touched in total; the ten nodes _below_ the two tags still hold their
old sums. They are stale, but harmlessly so — the tags above them record the
correction, and no read can reach a stale node without first passing a tag.

$$
% caption: Snapshot after $\textsc{RangeAdd}(0,5,+5)$. The two canonical nodes absorb the
%          update eagerly (sum $+\,5 \cdot \mathit{len}$) and hold a $+5$ tag; their
%          ancestors are recomputed on the way out. Everything beneath a tag (grey) is
%          stale, and stays stale until a later descent pushes the tag down.
\begin{tikzpicture}[
  every node/.style={draw, minimum width=9mm, minimum height=6mm, inner sep=1.5pt, font=\footnotesize},
  level 1/.style={sibling distance=56mm},
  level 2/.style={sibling distance=28mm},
  level 3/.style={sibling distance=14mm},
  level distance=12mm,
  edge from parent/.style={draw, -}]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw=acc, dashed] {61}
    child {node[draw=acc, very thick, fill=acc!15] {29: +5}
      child {node[black!55] {4}
        child {node[black!55] {3}}
        child {node[black!55] {1}}
      }
      child {node[black!55] {5}
        child {node[black!55] {4}}
        child {node[black!55] {1}}
      }
    }
    child {node[draw=acc, dashed] {32}
      child {node[draw=acc, very thick, fill=acc!15] {24: +5}
        child {node[black!55] {5}}
        child {node[black!55] {9}}
      }
      child {node {8}
        child {node {2}}
        child {node {6}}
      }
    };
  % leaf indices
  \foreach \x/\i in {-4.9/0, -3.5/1, -2.1/2, -0.7/3, 0.7/4, 2.1/5, 3.5/6, 4.9/7} {
    \node[draw=none, font=\scriptsize, black] at (\x, -4.1) {\i};
  }
\end{tikzpicture}
$$

Now query $\textsc{Sum}(2, 7)$ against this state. The recursion enters the
root and must descend _past_ the tagged node $[0,3]$, because $[0,3]$ straddles
$[2,7]$. Before recursing, it pushes the tag down: $[0,1]$ gets sum $4 + 5
\cdot 2 = 14$ and tag $+5$; $[2,3]$ gets sum $5 + 5 \cdot 2 = 15$ and tag $+5$;
the tag on $[0,3]$ is cleared. The query then proceeds normally — $[2,3]$ is
inside and returns $15$; on the right, $[4,7]$ is inside and returns $32$
without touching the tag below it. The answer is $15 + 32 = 47$, which
checks out against the updated array $[8,6,9,6,10,14,2,6]$: $9 + 6 + 10 + 14 +
2 + 6 = 47$.

Two details make the scheme correct in general. First, tags must **compose**:
two pending $+5$ and $+3$ tags on the same node collapse to $+8$, so a node
never holds more than one tag. Second, a node's stored aggregate is always
_correct for its own subtree assuming all tags strictly above it have been
applied_ — that is the invariant the push-down preserves, and it is what lets
a canonical node answer a query without any descent.

> **Invariant.** Every node's aggregate equals the true aggregate of its range
> after applying all tags on its ancestors. Push-down moves a tag one level
> deeper without changing any node's implied value, so queries that stop at
> canonical nodes read correct sums.

With lazy tags both **range update** and **range query** run in $O(\log n)$. This
is the segment tree's decisive advantage over the Fenwick tree: it supports
non-invertible aggregates ($\min$, $\max$) _and_ whole-range modifications, at the
cost of more memory and a more involved implementation.[^erickson-segment]

::impl{algo="lazy_segment_tree"}

## Choosing between them

Both give $O(\log n)$ point-update and $O(\log n)$ range-query; the choice is
about generality versus footprint.

- **Fenwick tree.** Pick it when the aggregate is an **invertible** group
  operation (sum, xor) and you only need point updates. It is a single array,
  cache-friendly, a dozen lines of code, and the constant factors are tiny. Range
  sum is $\text{prefix}(r) - \text{prefix}(l-1)$.
- **Segment tree.** Pick it when you need **$\min/\max/\gcd$** or any
  non-invertible aggregate, or **range updates** via lazy propagation. It is
  strictly more general, and you pay for it with $\sim 2$ to $4\times$ the memory and
  a more involved implementation.

One extension stretches the Fenwick tree further than it first appears. To
support **range update + point query** for sums, keep a Fenwick tree over the
_difference array_ $D[i] = A[i] - A[i-1]$: adding $\delta$ to $A[l\dots r]$
becomes two point updates ($D[l] \mathrel{+}= \delta$, $D[r+1] \mathrel{-}=
\delta$), and reading $A[i]$ becomes $\textsc{PrefixSum}(i)$. With a second
Fenwick tree tracking a correction term, even range update + range _sum_ works.
What no Fenwick variant recovers is a non-invertible aggregate — a range
$\min$ cannot be assembled from prefix information, because $\min$ has no
inverse to subtract with.

| workload | structure |
| --- | --- |
| point update, range sum / xor | Fenwick tree |
| range add, point read | Fenwick tree over the difference array |
| point update, range $\min/\max/\gcd$ | segment tree |
| range update, range query | segment tree with lazy propagation |

In short: Fenwick is the specialist, the segment tree the
generalist. For `range-sum-query-mutable`, a Fenwick tree
suffices; when the skyline or a range-assign problem demands $\max$ over a
mutable range, use the segment tree with lazy propagation.

## The segment tree's larger family

Neither structure is in the classic textbooks; they come from competitive
programming and the systems literature, and both extend into a large
family of range-query structures.

**Persistence and offline queries.** Because a point update touches only the
$O(\log n)$ nodes on one root-to-leaf path, a segment tree is naturally made
**persistent** by path-copying (the same trick that persists a balanced BST):
each update spawns a new version in $O(\log n)$ extra space, and old versions stay
queryable. A **persistent segment tree** answers offline questions like "the
$k$-th smallest value in the subarray $A[l\dots r]$" by querying the difference of
two versions, a standard tool for range-rank queries.

**When $O(\log n)$ per side isn't enough.** For simpler needs, **sqrt
decomposition** splits the array into $\sqrt n$ blocks and answers range queries
in $O(\sqrt n)$ with almost no code, sometimes the pragmatic choice for
non-associative or awkward aggregates. At the other extreme, **segment tree
beats** (Ji Ruyi's technique) supports range operations like "clamp every element
to at most $x$" in amortized $O(\log^2 n)$, which no lazy tag alone can do, by
storing the two largest distinct values per node and pruning branches where the
update is a no-op.

**Higher dimensions and richer keys.** The 2-D Fenwick tree in this lesson
generalizes to a Fenwick tree of Fenwick trees for $O(\log^2 n)$ rectangle sums,
and a **merge-sort tree** (a segment tree whose nodes store sorted subarrays)
answers "how many values in $A[l\dots r]$ are $\le x$" in $O(\log^2 n)$. The
common thread: any aggregate you can compute from two children in $O(1)$ slots
into the segment tree's divide-and-combine skeleton.[^btb-fenwick]

## Takeaways

- A static **prefix-sum array** answers range sums in $O(1)$ but updates in
  $O(n)$; a plain array updates in $O(1)$ but sums in $O(n)$. **Fenwick** and
  **segment** trees achieve **both in $O(\log n)$**.
- A **Fenwick tree** is a 1-indexed array where $F[i]$ holds the sum of the block
  $(\,i - \lowbit(i),\ i\,]$, with $\lowbit(i) = i
  \mathbin{\&} (-i)$. Prefix sum walks **down** clearing low bits; update walks
  **up** adding low bits, each $O(\log n)$.
- Fenwick range sum relies on **invertibility**: $\text{prefix}(r) -
  \text{prefix}(l-1)$. It fails for $\min/\max$.
- A **segment tree** stores each node's range aggregate (any **associative**
  op). Build $O(n)$, point update $O(\log n)$, and **range query** $O(\log n)$ by
  decomposing $[l,r]$ into $O(\log n)$ **canonical nodes**.
- **Lazy propagation** defers a range update by tagging canonical nodes and
  pushing tags down only when needed, giving $O(\log n)$ **range update + range
  query**.
- **Fenwick** = tiny, fast, sum-like invertible aggregates; **segment tree** =
  general $\min/\max$ and lazy range ops, at $\sim 2$ to $4\times$ the memory.

[^clrs-augment]: **CLRS**, Ch. 14, Augmenting Data Structures (§14.2): attach summary fields to nodes and maintain them through updates, the general method both structures specialize.
[^skiena-fenwick]: **Skiena**, §3.x, Range Queries / Augmented Structures: the binary indexed tree as a minimal-overhead structure for dynamic prefix sums.
[^erickson-segment]: **Erickson**, Ch., Data Structures: segment trees over canonical ranges, range decomposition, and lazy propagation for range updates.
[^btb-fenwick]: Fenwick, "A new data structure for cumulative frequency tables" (1994), the binary indexed tree; the persistent segment tree, sqrt decomposition, segment-tree-beats, and merge-sort-tree techniques are standard in the competitive-programming literature (e.g. the CP-Algorithms references).