Segment trees and Fenwick trees

advancedCommon atGoogleJane StreetCitadelMetaRead firstPrefix sumsBinary treesDivide and conquerPractise in the Sandbox →

A segment tree stores, for every node, a summary (sum, min, max, …) of one contiguous range of the array; the root covers everything and each child covers half its parent. A range query combines O(log n) whole nodes, and a point update rewrites the O(log n) nodes on one root-to-leaf path. A Fenwick tree (binary indexed tree) does prefix sums and point updates in O(log n) with a single array and two lines of bit arithmetic, but only for operations you can “subtract” (sums, counts, XOR).

The idea in plain words

Imagine a company with 8 shops reporting daily sales. The CEO asks “total sales of shops 2 through 6?” many times a day, and shop numbers change every few minutes.

• Add it up each time: cheap to update, O(n) per question.
• Prefix sums (P[i] = shops 0..i): O(1) per question, but one shop’s change shifts every prefix after it. O(n) per update.
• Regional managers: shops are paired under managers, pairs under area managers, areas under a director. Each manager knows their region’s total. To answer “shops 2..6”, ask the few managers whose regions fit inside the range. When shop 3 changes, only shop 3’s manager chain (one per level) recomputes.

The regional-manager hierarchy is a segment tree. Its trick is that any range splits into at most about 2·log₂ n whole regions, and any single position belongs to exactly one region per level. Both numbers are logarithmic, so both operations are.

See it

Run a range sum and watch each node classify itself: inside the query (use its sum and stop), outside (skip its whole subtree), or partial (ask both children). Then update one element and watch only one path change.

Segment tree: range sum and point update

interactive

array (2-10 values)

 build

lr

querysum(l, r)

ivalue

updatea[i] = value

5

2

7

1

3

6

4

8

01234567

nodes touched0

tree height3

used whole / updatedpartial overlap: splitoutside: skippedcurrentpath / query range

Each node stores the sum of the range under it (shown below the node). Leaves are the array itself.

↺◀▶ Play▶1 / 1

Operation log

Query sum(2, 6), then set a[3] = 9 and query again.

Things to try:

• Query sum(0, 7): the root alone answers it. Query sum(3, 3): a single path down to one leaf.
• Query sum(1, 6) on 8 elements. Count the green nodes: never more than two per level.
• Build a 10-element array. The tree isn’t perfect any more, and nothing breaks.

When to reach for it

The problem says…	Why a segment / Fenwick tree fits
“range sum / min / max / gcd and point updates, interleaved”	Both operations O(log n); prefix sums would make updates O(n).
“add x to every element in [l, r]” plus range queries	A segment tree with lazy propagation keeps both O(log n).
many queries, no updates	Don’t. Prefix sums (sum) or a sparse table (min/max) are simpler and O(1) per query. See prefix sums.
updates and queries known up front, with a simple operation	Often an offline sort plus a Fenwick tree is the shortest correct code.

Requirements on the operation

A segment tree needs an associative combine with an identity: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). Sum, min, max, gcd, product, XOR and “merge two sorted summaries” all qualify. A Fenwick tree additionally needs an inverse (to turn two prefix answers into a range answer), so it works for sum and XOR, but not for min or max over arbitrary ranges.

How it works

Segment tree

1. Build: leaves hold the array. Each inner node = combine(left child, right child). Build bottom-up in O(n); there are about 2n nodes.
2. Query [l, r] at a node covering [s, e]: if [s, e] is outside [l, r], return the identity (0 for sums). If it’s fully inside, return the node’s stored value. Otherwise split: query both children and combine.
3. Point update a[i] = v: set the leaf, then walk up to the root, recomputing each ancestor from its two children.
4. Why O(log n) for queries: at each level, at most two nodes are partially covered (the ones containing l and r). Only they recurse; everything else stops immediately.

The building blocks: the array layout (node i has children 2i and 2i+1, leaves in the second half), a bottom-up build, and a point update that climbs to the root. The query is the recursion described in step 2.

Python

build_update.py

def build(a: list[int]) -> list[int]:
    """Iterative (bottom-up) segment tree for sums. Node i has children 2i and 2i+1."""
    n = len(a)
    tree = [0] * (2 * n)
    tree[n:] = a                              # 1. leaves live in tree[n .. 2n-1]
    for i in range(n - 1, 0, -1):             # 2. each parent = sum of its two children,
        tree[i] = tree[2 * i] + tree[2 * i + 1]   # built right to left so children exist
    return tree                               # tree[1] is the root: the sum of everything


def point_set(tree: list[int], n: int, i: int, value: int) -> None:
    i += n
    tree[i] = value                           # 3. overwrite the leaf
    while i > 1:                              # 4. climb to the root, refreshing each ancestor
        i //= 2
        tree[i] = tree[2 * i] + tree[2 * i + 1]


def check(tree: list[int], n: int) -> bool:
    """The invariant every query relies on: each inner node is the sum of its children."""
    return all(tree[i] == tree[2 * i] + tree[2 * i + 1] for i in range(1, n))


if __name__ == "__main__":
    a = [5, 2, 7, 1, 3, 6, 4, 8]
    t = build(a)
    assert t[1] == sum(a) == 36 and check(t, len(a))
    point_set(t, len(a), 3, 9)                # a[3]: 1 -> 9
    assert t[1] == 44 and check(t, len(a))
    t2 = build([4, 1, 3])                     # n need not be a power of two
    assert t2[1] == 8 and check(t2, 3)
    print("ok")

TypeScript

build_update.ts

import assert from "node:assert/strict";

/** Iterative (bottom-up) segment tree for sums. Node i has children 2i and 2i+1. */
export function build(a: number[]): number[] {
  const n = a.length;
  const tree = new Array<number>(2 * n).fill(0);
  for (let i = 0; i < n; i++) tree[n + i] = a[i]; // 1. leaves live in tree[n .. 2n-1]
  for (let i = n - 1; i >= 1; i--) tree[i] = tree[2 * i] + tree[2 * i + 1]; // 2. parent = sum of children
  return tree; // tree[1] is the root: the sum of everything
}

export function pointSet(tree: number[], n: number, i: number, value: number): void {
  i += n;
  tree[i] = value; // 3. overwrite the leaf
  while (i > 1) { // 4. climb to the root, refreshing each ancestor
    i >>= 1;
    tree[i] = tree[2 * i] + tree[2 * i + 1];
  }
}

/** The invariant every query relies on: each inner node is the sum of its children. */
const check = (tree: number[], n: number) =>
  Array.from({ length: n - 1 }, (_, k) => k + 1).every((i) => tree[i] === tree[2 * i] + tree[2 * i + 1]);

const a = [5, 2, 7, 1, 3, 6, 4, 8];
const t = build(a);
assert.ok(t[1] === 36 && check(t, a.length));
pointSet(t, a.length, 3, 9); // a[3]: 1 -> 9
assert.ok(t[1] === 44 && check(t, a.length));
const t2 = build([4, 1, 3]); // n need not be a power of two
assert.ok(t2[1] === 8 && check(t2, 3));
console.log("ok");

C#

build_update.cs

int[] a = [5, 2, 7, 1, 3, 6, 4, 8];
var t = Build(a);
if (t[1] != 36 || !Check(t, a.Length)) throw new Exception("build");
PointSet(t, a.Length, 3, 9);                      // a[3]: 1 -> 9
if (t[1] != 44 || !Check(t, a.Length)) throw new Exception("update");
var t2 = Build([4, 1, 3]);                        // n need not be a power of two
if (t2[1] != 8 || !Check(t2, 3)) throw new Exception("odd n");
Console.WriteLine("ok");

// Iterative (bottom-up) segment tree for sums. Node i has children 2i and 2i+1.
static long[] Build(int[] a)
{
    int n = a.Length;
    var tree = new long[2 * n];
    for (int i = 0; i < n; i++) tree[n + i] = a[i];               // 1. leaves live in tree[n .. 2n-1]
    for (int i = n - 1; i >= 1; i--) tree[i] = tree[2 * i] + tree[2 * i + 1]; // 2. parent = sum of children
    return tree;                                                  // tree[1] is the root
}

static void PointSet(long[] tree, int n, int i, long value)
{
    i += n;
    tree[i] = value;                              // 3. overwrite the leaf
    while (i > 1)                                 // 4. climb to the root, refreshing each ancestor
    {
        i >>= 1;
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
}

// The invariant every query relies on: each inner node is the sum of its children.
static bool Check(long[] tree, int n) =>
    Enumerable.Range(1, n - 1).All(i => tree[i] == tree[2 * i] + tree[2 * i + 1]);

Two layouts

The recursive layout (root at index 1, ranges split at the midpoint, arrays sized 4n to be safe) is the one most people write and the easiest to extend with lazy propagation. The iterative bottom-up layout above (size 2n, leaves at n..2n−1) is shorter and faster, with a query that walks two pointers upward from both ends. Know one well.

Fenwick tree (binary indexed tree)

A Fenwick tree is a cleverer, smaller cousin. It’s a 1-based array T where cell i stores the sum of a block ending at i whose length is lowbit(i), the value of i’s lowest set bit (i & -i). So T[12] (12 = 1100₂) covers 4 elements, a[9..12]; T[13] covers just a[13]; T[8] covers a[1..8].

Fenwick tree: every cell covers a power-of-two block

step through

i (1-16)

T[16]=80

T[8]=31

T[4]=9

T[12]=21

T[2]=4

T[6]=14

T[10]=8

T[14]=16

T1

T3

T5

T7

T9

T11

T13

T15

3

1

4

1

5

9

2

6

5

3

5

8

9

7

9

3

1
00001

2
00010

3
00011

4
00100

5
00101

6
00110

7
00111

8
01000

9
01001

10
01010

11
01011

12
01100

13
01101

14
01110

15
01111

16
10000

i13 = 01101₂

lowbit1

total0

jumps0

current cellcells usedprefix being summedposition updated

prefix(13) = a[1] + … + a[13]. Start at T[13] and keep removing the lowest set bit.

↺◀▶ Play▶1 / 5

1. Prefix sum of [1..i]: add T[i], then jump to i − lowbit(i) (strip the lowest 1-bit) and repeat until 0. One jump per 1-bit of i.
2. Point update at i: add δ to T[i], then jump to i + lowbit(i) and repeat while ≤ n. Each jump lands on the next bigger block that still contains i.
3. Range sum [l, r] = prefix(r) − prefix(l − 1). This is where the inverse is needed.

Both walks are pure index arithmetic, and that arithmetic is the whole data structure:

Python

fenwick_paths.py

def lowbit(i: int) -> int:
    return i & -i                     # lowest set bit: 12 = 0b1100 -> 4


def prefix_path(i: int) -> list[int]:
    """Cells a 1-based Fenwick prefix query over [1..i] reads: strip the lowest bit each step."""
    out = []
    while i > 0:
        out.append(i)                 # cell i covers (i - lowbit(i), i]
        i -= lowbit(i)
    return out


def update_path(i: int, n: int) -> list[int]:
    """Cells a point update at position i touches: add the lowest bit each step."""
    out = []
    while i <= n:
        out.append(i)
        i += lowbit(i)
    return out


if __name__ == "__main__":
    assert lowbit(12) == 4 and lowbit(7) == 1
    assert prefix_path(13) == [13, 12, 8]       # (12,13] + (8,12] + (0,8] = [1..13]
    assert update_path(5, 16) == [5, 6, 8, 16]
    for i in range(1, 65):                      # the ranges always tile [1..i] exactly
        covered = sorted(k for c in prefix_path(i) for k in range(c - lowbit(c) + 1, c + 1))
        assert covered == list(range(1, i + 1))
        assert all(c - lowbit(c) < i <= c for c in update_path(i, 64))  # each contains i
    print("ok")

TypeScript

fenwick_paths.ts

import assert from "node:assert/strict";

export const lowbit = (i: number): number => i & -i; // lowest set bit: 12 = 0b1100 -> 4

/** Cells a 1-based Fenwick prefix query over [1..i] reads: strip the lowest bit each step. */
export function prefixPath(i: number): number[] {
  const out: number[] = [];
  for (; i > 0; i -= lowbit(i)) out.push(i); // cell i covers (i - lowbit(i), i]
  return out;
}

/** Cells a point update at position i touches: add the lowest bit each step. */
export function updatePath(i: number, n: number): number[] {
  const out: number[] = [];
  for (; i <= n; i += lowbit(i)) out.push(i);
  return out;
}

assert.ok(lowbit(12) === 4 && lowbit(7) === 1);
assert.deepEqual(prefixPath(13), [13, 12, 8]); // (12,13] + (8,12] + (0,8] = [1..13]
assert.deepEqual(updatePath(5, 16), [5, 6, 8, 16]);
for (let i = 1; i <= 64; i++) { // the ranges always tile [1..i] exactly
  const covered = prefixPath(i).flatMap((c) => Array.from({ length: lowbit(c) }, (_, k) => c - k)).sort((x, y) => x - y);
  assert.deepEqual(covered, Array.from({ length: i }, (_, k) => k + 1));
  assert.ok(updatePath(i, 64).every((c) => c - lowbit(c) < i && i <= c)); // each contains i
}
console.log("ok");

C#

fenwick_paths.cs

if (Lowbit(12) != 4 || Lowbit(7) != 1) throw new Exception("lowbit");
if (!PrefixPath(13).SequenceEqual([13, 12, 8])) throw new Exception("prefix path"); // (12,13] + (8,12] + (0,8]
if (!UpdatePath(5, 16).SequenceEqual([5, 6, 8, 16])) throw new Exception("update path");
for (int i = 1; i <= 64; i++)                     // the ranges always tile [1..i] exactly
{
    var covered = PrefixPath(i).SelectMany(c => Enumerable.Range(c - Lowbit(c) + 1, Lowbit(c))).Order();
    if (!covered.SequenceEqual(Enumerable.Range(1, i))) throw new Exception($"tiling {i}");
    if (!UpdatePath(i, 64).All(c => c - Lowbit(c) < i && i <= c)) throw new Exception($"contains {i}");
}
Console.WriteLine("ok");

static int Lowbit(int i) => i & -i;               // lowest set bit: 12 = 0b1100 -> 4

// Cells a 1-based Fenwick prefix query over [1..i] reads: strip the lowest bit each step.
static List<int> PrefixPath(int i)
{
    var output = new List<int>();
    for (; i > 0; i -= Lowbit(i)) output.Add(i);  // cell i covers (i - lowbit(i), i]
    return output;
}

// Cells a point update at position i touches: add the lowest bit each step.
static List<int> UpdatePath(int i, int n)
{
    var output = new List<int>();
    for (; i <= n; i += Lowbit(i)) output.Add(i);
    return output;
}

What it costs

	Build	Range query	Point update	Range update	Memory
Recompute each time		O(n)	O(1)	O(n)	O(n)
Prefix-sum array	O(n)	O(1)	O(n)	O(n)	O(n)
Segment tree	O(n)	O(log n)	O(log n)	O(log n) with lazy	~2n to 4n nodes
Fenwick tree	O(n) or O(n log n)	O(log n) (invertible ops)	O(log n)	O(log n) for some ops	n + 1
Sparse table (min/max, static)	O(n log n)	O(1)	not supported	not supported	n log n

Why log n: a segment tree has ⌈log₂ n⌉ levels and an update changes one node per level. A Fenwick query does one jump per 1-bit of i (at most ⌊log₂ n⌋ + 1); an update’s block sizes at least double each jump.

In practice a Fenwick tree is 2-3× faster than a recursive segment tree and far less code. A segment tree is more general: any associative operation, lazy range updates, and “descend to find the first index where…” searches.

Variations you’ll meet

• Range min / max. Same tree, combine = min/max, identity = +∞/−∞. No Fenwick equivalent for arbitrary ranges.
• Lazy propagation. For “add x to every element in [l, r]”, tag fully covered nodes with a pending add and push it to the children only when you later need to go below them. Keeps range updates O(log n).
• Storing more per node. A node can hold a small struct, e.g. (best, prefix best, suffix best, total) for “maximum subarray sum in a range”. The art is designing a combine that merges two children correctly.
• Descending the tree. “Find the first index where the prefix sum reaches k” walks down one path in O(log n) instead of binary-searching over O(log n) queries.
• Fenwick over values. Index by value instead of position (after compressing values to 1..m). Then prefix(x) counts how many seen values are ≤ x.
• 2-D Fenwick tree. Nested loops over both indices: O(log n · log m) for submatrix sums with point updates.
• Persistent / merge-sort trees. Keep old versions, or sorted lists in nodes. Rare outside competitive programming.

Pitfalls

• Reaching for it when there are no updates. Prefix sums are O(1) per query and 3 lines.
• Off-by-one in Fenwick indexing. It’s 1-based. Index 0 loops forever on i += i & -i (lowbit(0) = 0). Shift input indices by one.
• Inclusive vs exclusive ranges. Decide whether [l, r] or [l, r) and stay consistent between query and recursion.
• Wrong identity. Out-of-range nodes must return 0 for sum, +∞ for min, −∞ for max. Returning 0 for min is a classic bug.
• Recursive array size. The recursive layout needs up to 4n cells for arbitrary n, not 2n.
• Using Fenwick for min/max ranges. It can’t subtract a minimum. Use a segment tree.
• Overflow in C#/TS with large sums: use long / BigInt-aware reasoning. JS numbers are exact only up to 2⁵³.

In the interview

• Start by asking: how many updates vs queries? are updates point or range? which operation (sum, min, …)? n up to? If there are no updates, say “prefix sums” and you’re done.
• Name the trade-off: “A Fenwick tree is enough for sums and is less code; if we later need min or range updates I’d switch to a segment tree.”
• State the bound with the reason: “At most two partial nodes per level, so a query touches O(log n) nodes.”
• Expect follow-ups: “Now support adding to a whole range” (lazy propagation), “Now return the index where the prefix sum first exceeds k” (descend), “What if values are huge but there are few distinct ones?” (coordinate compression).

Check yourself

Check yourself

pick one

You have 10⁵ elements and 10⁵ operations, half point updates and half range-sum queries. Why not just keep a prefix-sum array?

APrefix sums cannot answer range queriesBEach update must rewrite every prefix after it, O(n), so the total is about 5×10⁹ stepsCPrefix sums use too much memoryDPrefix sums are fine here

Check yourself

pick one

A Fenwick tree answers prefix(13). Which cells does it read?

AT[13] onlyBT[13], T[12], T[8]CT[1] through T[13]DT[13], T[14], T[16]

Check yourself

pick one

Which of these can a plain Fenwick tree answer for an arbitrary range [l, r] with point updates?

AMinimumBMaximumCSumDMedian

Practice on your own

These are classic textbook exercises, not gym questions:

• Range XOR queries with point updates (Fenwick tree; XOR is its own inverse).
• Range GCD queries with point updates (segment tree; GCD is associative but has no inverse).
• Maximum subarray sum within [l, r], with point updates (store four values per node).
• Longest run of consecutive 1s within [l, r] of a bit array, with bit flips.
• Submatrix sums with point updates using a 2-D Fenwick tree.

Go deeper

• cp-algorithms: Segment Tree: recursive layout, lazy propagation, descending, many variants.
• cp-algorithms: Fenwick Tree: 0- and 1-based versions, range updates, 2-D.
• Fenwick, P. M. (1994), “A New Data Structure for Cumulative Frequency Tables”, Software: Practice and Experience 24(3): the original paper.
• Al.Cash, “Efficient and easy segment trees” (Codeforces blog): the iterative 2n bottom-up layout used above.

Related

Prefix sumsThe no-updates answer, and the idea Fenwick trees extend.

Bit manipulationWhy i & -i isolates the lowest set bit.

Divide and conquerThe split-in-half recursion behind segment trees.

Binary treesArray layouts and recursive traversals.