Fenwick & Segment Trees

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 $P[i]=A[1]+\cdots +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)$.

The idea, in the spirit of the previous lessons on augmenting trees with subtree summaries,¹ 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 $\mathrm{lowbit}(i)$, the value of the lowest set bit of $i$:

That is, $F[i]$ covers the half-open range $\left(i-\mathrm{lowbit}(i),i\right)$. 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:

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=(x1\underset{t}{\underbrace{0\cdots 0}}{)}_2$. Flipping gives $(\bar{x}01\cdots 1{)}_2$, and adding $1$ carries through the trailing ones and stops at the flipped $0$: $-i=(\bar{x}10\cdots 0{)}_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: $\mathrm{lowbit}(6)=2$ since $6=(110{)}_2$, so $F[6]$ covers indices $5\dots 6$; $\mathrm{lowbit}(8)=8$ since $8=(1000{)}_2$, so $F[8]$ covers the whole prefix $1\dots 8$; and $\mathrm{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:

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]+\cdots +A[4]=9$. Nothing else is stored — the structure is this one array.

Prefix sum. To compute $P[i]=A[1]+\cdots +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-\mathrm{lowbit}(i)$, so we jump there and repeat, clearing one set bit each step until we reach $0$.

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

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\dots 6]$, $F[4]$ covers $A[1\dots 4]$. The three blocks tile $A[1\dots 7]$ 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$:

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\leftarrow i+\mathrm{lowbit}(i)$ moves to the next larger block that covers $k$, until we run past $n$.

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

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

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

A range sum is then two prefix queries:

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

The implicit tree

The array $F$ is a flattened forest, and seeing the tree explains both walks. Define $\mathrm{parent}(i)=i+\mathrm{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:

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

The two operations are just the two natural walks in this forest. $\text{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$. $\text{PrefixSum}(i)$ hops across the forest from one subtree root to the next one on its left; each hop $i\leftarrow i-\mathrm{lowbit}(i)$ discards a fully-counted subtree. Since $\mathrm{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\leftarrow A$, then for $i=1,\dots ,n$ add $F[i]$ into $F[i+\mathrm{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 $\text{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.

class Fenwick:
  """
    1-indexed internally; the public API is 0-indexed over `size` slots.\n
  """

  def __init__(self, size: int) -> None:
    self.size: int = size
    self._tree: list[float] = [0.0 for _ in range(size + 1)]

  def add(self, index: int, delta: float) -> None:
    """
      Add `delta` to the element at `index` (0-indexed).\n
    """
    # walk to each slot whose partial sum covers `index`, climbing by low bit.
    position: int = index + 1
    while position <= self.size:
      self._tree[position] += delta
      position += position & (-position)

  def prefix_sum(self, count: int) -> float:
    """
      Sum of the first `count` elements — the range `[0, count)`.\n
    """
    # accumulate the partial sums covering [0, count), stepping down by low bit.
    position: int = min(count, self.size)
    total: float = 0.0
    while position > 0:
      total += self._tree[position]
      position -= position & (-position)
    return total

  def range_sum(self, low: int, high: int) -> float:
    """
      Sum of the elements in `[low, high)`.\n
    """
    return self.prefix_sum(high) - self.prefix_sum(low)

class Fenwick2D:
  """
    1-indexed internally; the public API is 0-indexed over `rows` x `columns`.\n
  """

  def __init__(self, rows: int, columns: int) -> None:
    self.rows: int = rows
    self.columns: int = columns
    self._tree: list[list[float]] = [
      [0.0 for _ in range(columns + 1)] for _ in range(rows + 1)
    ]

  def add(self, row: int, column: int, delta: float) -> None:
    """
      Add `delta` to the cell at `(row, column)` (both 0-indexed).\n
    """
    # walk both axes upward, adding delta to every covering rectangle.
    outer: int = row + 1
    while outer <= self.rows:
      inner: int = column + 1
      while inner <= self.columns:
        self._tree[outer][inner] += delta
        inner += inner & (-inner)
      outer += outer & (-outer)

  def prefix_sum(self, row_count: int, column_count: int) -> float:
    """
      Sum over the rectangle `[0, row_count) x [0, column_count)` — the\n
      cells above and to the left of the given corner.\n
    """
    # walk both axes downward, summing the partial rectangles along the way.
    outer: int = min(row_count, self.rows)
    total: float = 0.0
    while outer > 0:
      inner: int = min(column_count, self.columns)
      while inner > 0:
        total += self._tree[outer][inner]
        inner -= inner & (-inner)
      outer -= outer & (-outer)

    return total

  def range_sum(
    self,
    low_row: int,
    low_column: int,
    high_row: int,
    high_column: int,
  ) -> float:
    """
      Sum over the half-open rectangle\n
      `[low_row, high_row) x [low_column, high_column)`,\n
      by inclusion-exclusion of four corner prefix sums.\n
    """
    return (
      self.prefix_sum(high_row, high_column)
      - self.prefix_sum(low_row, high_column)
      - self.prefix_sum(high_row, low_column)
      + self.prefix_sum(low_row, low_column)
    )

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.

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\}$.

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 $\text{Sum}(1,5)$ and record every node the recursion touches:

The answer is $1+5+14=20$, and directly: $A[1]+\cdots +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.

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]\leftarrow 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.

from collections.abc import Callable, Sequence
from typing import Generic, TypeVar

Value = TypeVar("Value")

def _add(left: float, right: float) -> float:
  """
    Default combine operation: numeric addition (range-sum trees).\n
  """
  return left + right

class SegmentTree(Generic[Value]):
  """
    A range-aggregate tree; defaults to range-sum over numbers.\n
  """

  def __init__(
    self,
    data: Sequence[Value],
    combine: Callable[[Value, Value], Value] = _add,
    identity: Value = 0,
  ) -> None:
    """
      Build the tree over `data` for the aggregate `combine`, whose\n
      neutral element is `identity` (0 for sum, +inf for min, …).\n
    """
    # store the aggregate and its identity for later queries.
    self.size: int = len(data)
    self._combine: Callable[[Value, Value], Value] = combine
    self._identity: Value = identity

    # leaves live in the back half; internal nodes start as identity.
    self._tree: list[Value] = [identity for _ in range(2 * self.size)]
    self._tree[self.size:] = list(data)

    # fill internal nodes bottom-up, each the combine of its two children.
    for parent in range(self.size - 1, 0, -1):
      self._tree[parent] = combine(
        self._tree[2 * parent],
        self._tree[2 * parent + 1],
      )

  def update(self, index: int, value: Value) -> None:
    """
      Set the element at `index` to `value`, refreshing its ancestors.\n
    """
    # write the new value at its leaf.
    position: int = index + self.size
    self._tree[position] = value

    # walk to the root, recombining each ancestor from its children.
    position //= 2
    while position >= 1:
      self._tree[position] = self._combine(
        self._tree[2 * position],
        self._tree[2 * position + 1],
      )
      position //= 2

  def query(self, low: int, high: int) -> Value:
    """
      Aggregate over the half-open range `[low, high)`.\n
    """
    # start at the leaf bounds of the range.
    result: Value = self._identity
    left: int = low + self.size
    right: int = high + self.size

    # climb both ends inward, folding in any node that falls outside its parent.
    while left < right:
      if left & 1:
        result = self._combine(result, self._tree[left])
        left += 1
      if right & 1:
        right -= 1
        result = self._combine(result, self._tree[right])
      left //= 2
      right //= 2

    return result

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.

A worked range update

Run $\text{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 $len$ cells adds $5\cdot len$) and record the tag:

• $[0,3]$: sum $9\leftarrow 9+5\cdot 4=29$, tag $\leftarrow +5$;
• $[4,5]$: sum $14\leftarrow 14+5\cdot 2=24$, tag $\leftarrow +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.

Now query $\text{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.

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.³

from collections.abc import Sequence
from typing import Optional

class SegmentNode:
  """
    One node of the tree: the half-open-free, inclusive interval `[low, high]`\n
    it spans, the sum over that interval, a pending `lazy` add not yet pushed\n
    to its children, and links to the left and right child nodes.\n
    A node is a leaf exactly when `low == high`.\n
  """

  def __init__(self, low: int, high: int) -> None:
    self.low: int = low
    self.high: int = high
    self.total: int = 0
    self.lazy: int = 0
    self.left: Optional[SegmentNode] = None
    self.right: Optional[SegmentNode] = None

  @property
  def is_leaf(self) -> bool:
    """
      Whether this node covers a single array element.\n
    """
    return self.low == self.high

  def __repr__(self) -> str:
    return f"SegmentNode([{self.low}, {self.high}], total={self.total})"

class LazySegmentTree:
  """
    A range-add / range-sum tree over a fixed-length integer array.\n
    `update(low, high, delta)` adds `delta` to every element in the\n
    inclusive range `[low, high]`; `query(low, high)` returns their sum.\n
  """

  def __init__(self, data: Sequence[int]) -> None:
    """
      Build the tree over a copy of `data` in O(n).\n
      An empty sequence yields a tree whose every query returns 0.\n
    """
    self.size: int = len(data)
    self.root: Optional[SegmentNode] = (
      self._build(0, self.size - 1, data) if self.size > 0 else None
    )

  def _build(
    self,
    low: int,
    high: int,
    data: Sequence[int],
  ) -> SegmentNode:
    """
      Recursively construct the subtree spanning `[low, high]`, storing the\n
      true sum at every node bottom-up.\n
    """
    # a leaf spans one element and holds it directly.
    node = SegmentNode(low, high)
    if low == high:
      node.total = data[low]
      return node

    # split at the midpoint and build both halves.
    middle: int = (low + high) // 2
    node.left = self._build(low, middle, data)
    node.right = self._build(middle + 1, high, data)

    # carry the children's sums up to this node.
    node.total = node.left.total + node.right.total
    return node

  def _apply(self, node: SegmentNode, delta: int) -> None:
    """
      Add `delta` to every element under `node`: bump its sum by the count\n
      of elements it spans and stash the per-element tag for its children.\n
    """
    span: int = node.high - node.low + 1
    node.total += delta * span
    node.lazy += delta

  def _push_down(self, node: SegmentNode) -> None:
    """
      Flush a pending tag to both children, honoring the promise just in\n
      time, the moment a query or update needs to descend past `node`.\n
    """
    if node.lazy != 0 and node.left is not None and node.right is not None:
      self._apply(node.left, node.lazy)
      self._apply(node.right, node.lazy)
      node.lazy = 0

  def update(self, low: int, high: int, delta: int) -> None:
    """
      Add `delta` to every element in the inclusive range `[low, high]`.\n
    """
    if self.root is not None and low <= high:
      self._update(self.root, low, high, delta)

  def _update(
    self,
    node: SegmentNode,
    low: int,
    high: int,
    delta: int,
  ) -> None:
    """
      Apply the range add at `node`, tagging it whole when its interval\n
      lies inside `[low, high]` and otherwise recursing into the children\n
      whose intervals overlap the update range.\n
    """
    # disjoint: nothing under this node is touched.
    if high < node.low or node.high < low:
      return

    # canonical node: tag it whole instead of descending.
    if low <= node.low and node.high <= high:
      self._apply(node, delta)
      return

    # partial overlap: flush the tag, then recurse into both children.
    self._push_down(node)
    assert node.left is not None and node.right is not None
    self._update(node.left, low, high, delta)
    self._update(node.right, low, high, delta)

    # recompute this node's sum from the updated children.
    node.total = node.left.total + node.right.total

  def query(self, low: int, high: int) -> int:
    """
      Sum of the elements in the inclusive range `[low, high]`.\n
      An empty or out-of-order range sums to 0.\n
    """
    if self.root is None or low > high:
      return 0
    return self._query(self.root, low, high)

  def _query(self, node: SegmentNode, low: int, high: int) -> int:
    """
      Aggregate the canonical nodes covering `[low, high]`, pushing pending\n
      tags down as the recursion enters each subtree.\n
    """
    # disjoint contributes nothing; a canonical node contributes its sum.
    if high < node.low or node.high < low:
      return 0
    if low <= node.low and node.high <= high:
      return node.total

    # partial overlap: flush the tag, then sum both children.
    self._push_down(node)
    assert node.left is not None and node.right is not None
    return (
      self._query(node.left, low, high)
      + self._query(node.right, low, high)
    )

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]+=\delta$, $D[r+1]-=\delta$), and reading $A[i]$ becomes $\text{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.

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.⁴

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-\mathrm{lowbit}(i),i]$, with $\mathrm{lowbit}(i)=i\&(-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.