Segment Trees and Fenwick Trees | Algorithms

The café from Prefix Sums now has eight days of takings: 5, 2, 6, 3, 1, 4, 7, 2. The owner still asks things like "how much from day 3 to day 7?" all the time. But now the bookkeeper also keeps correcting old days: a refund here, a late receipt there.

Prefix sums answer a range question in O(1), but one correction to an early day changes every running total after it: O(n) per change. A plain array has the opposite problem: changes are O(1), but every sum is a loop. You want both fast.

The idea: precompute sums of blocks

Split the days in half, and each half in half again, down to single days. Store the total of every block. Now any range is a few whole blocks glued together, and a correction to one day only touches the blocks that contain it: one per level.

That is a segment tree. It is a binary tree where every node stores the sum of a range of the array. The root covers everything. Each node's left child covers the left half of its range, the right child the right half. The leaves are the single values.

It is stored in an array the same way as a heap: the children of node i sit at 2i + 1 and 2i + 2. For our eight days, node 0 covers indexes 0 to 7 and holds 30. Node 1 covers 0 to 3 (16), node 2 covers 4 to 7 (14), and so on down to the leaves at nodes 7 to 14.

Answering a range query

As in the Prefix Sums lesson, the array counts from 0, so days 3 to 7 are indexes 2 to 6. To get their sum, start at the root and ask each node one question: how does my range overlap the query?

Not at all: contribute 0 and stop.
Completely inside: contribute the stored sum and stop. No need to look below.
Partly: ask both children and add their answers.

Sum of indexes 2 to 6Use the arrows or ← → keys

query(node covering lo..hi):  if no overlap with left..right: return 0  if lo..hi is inside left..right: return tree[node]  return query(left child) + query(right child)

segment tree
node range
0..7
total
0
1The root covers 0..7. The query 2..6 only partly overlaps it, so split into both children.
segment tree
node range
0..3
total
0
2Node 1 covers 0..3. Partial overlap again, so split.
segment tree
node range
0..1
total
0
3Node 3 covers 0..1. That is entirely before index 2, so it adds 0 and we never look at its children.
segment tree
node range
2..3
total
9
4Node 4 covers 2..3, fully inside the query. Take its 9 (6 + 3) without visiting the leaves.
segment tree
node range
4..7
total
9
5Back up to the root's right child, node 2, covering 4..7. Partial overlap, so split.
segment tree
node range
4..5
total
14
6Node 5 covers 4..5, fully inside. Add 5.
segment tree
node range
6..7
total
14
7Node 6 covers 6..7. Partial: index 6 is in, index 7 is out. Split.
segment tree
node range
6..6
total
21
8Leaf 13 is index 6: inside, add 7. Leaf 14 is index 7: outside, add 0.
segment tree
total
21
blocks used
3
9The answer is 9 + 5 + 7 = 21, built from three stored blocks. Check: 6 + 3 + 1 + 4 + 7 = 21.

1 / 9

The query is O(log n). At each level of the tree, at most two nodes are partial: the ones containing the left and right edges of the query. Everything between them is fully inside and stops at once. So each level costs a small constant, and there are about log₂(n) levels.

Changing one value

The bookkeeper finds that day 3 (index 2) was really 11, not 6. Change the leaf, then walk up to the root, recomputing each parent as the sum of its two children. Only the blocks containing index 2 change.

Set index 2 to 11Use the arrows or ← → keys

segment tree
change
+5
1Index 2 is leaf 9. Its value goes from 6 to 11.
segment tree
change
+5
2Its parent, node 4 (range 2..3), becomes 11 + 3 = 14.
segment tree
change
+5
3Node 1 (range 0..3) becomes 7 + 14 = 21.
segment tree
nodes updated
4
4The root becomes 21 + 14 = 35. Four nodes changed, one per level. The other eleven are untouched because their ranges do not contain index 2.

1 / 4

Segment tree for range sums

class SegmentTree {
  constructor(values) {
    this.n = values.length;
    this.tree = new Array(4 * this.n).fill(0);
    if (this.n > 0) this.build(values, 0, 0, this.n - 1);
  }
  build(values, node, lo, hi) {
    if (lo === hi) { this.tree[node] = values[lo]; return; }
    const mid = Math.floor((lo + hi) / 2);
    this.build(values, 2 * node + 1, lo, mid);
    this.build(values, 2 * node + 2, mid + 1, hi);
    this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
  }
  // Sum of values[left..right], both included.
  query(left, right, node = 0, lo = 0, hi = this.n - 1) {
    if (right < lo || hi < left) return 0;                 // no overlap
    if (left <= lo && hi <= right) return this.tree[node]; // fully inside
    const mid = Math.floor((lo + hi) / 2);
    return this.query(left, right, 2 * node + 1, lo, mid) +
           this.query(left, right, 2 * node + 2, mid + 1, hi);
  }
  // Set values[index] = value.
  update(index, value, node = 0, lo = 0, hi = this.n - 1) {
    if (lo === hi) { this.tree[node] = value; return; }
    const mid = Math.floor((lo + hi) / 2);
    if (index <= mid) this.update(index, value, 2 * node + 1, lo, mid);
    else this.update(index, value, 2 * node + 2, mid + 1, hi);
    this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
  }
}

class SegmentTree:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (4 * self.n)
        if self.n > 0:
            self._build(values, 0, 0, self.n - 1)
 
    def _build(self, values, node, lo, hi):
        if lo == hi:
            self.tree[node] = values[lo]
            return
        mid = (lo + hi) // 2
        self._build(values, 2 * node + 1, lo, mid)
        self._build(values, 2 * node + 2, mid + 1, hi)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
 
    def query(self, left, right, node=0, lo=0, hi=None):
        """Sum of values[left..right], both included."""
        if hi is None:
            hi = self.n - 1
        if right < lo or hi < left:
            return 0                      # no overlap
        if left <= lo and hi <= right:
            return self.tree[node]        # fully inside
        mid = (lo + hi) // 2
        return (self.query(left, right, 2 * node + 1, lo, mid) +
                self.query(left, right, 2 * node + 2, mid + 1, hi))
 
    def update(self, index, value, node=0, lo=0, hi=None):
        """Set values[index] = value."""
        if hi is None:
            hi = self.n - 1
        if lo == hi:
            self.tree[node] = value
            return
        mid = (lo + hi) // 2
        if index <= mid:
            self.update(index, value, 2 * node + 1, lo, mid)
        else:
            self.update(index, value, 2 * node + 2, mid + 1, hi)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

Nothing here is specific to sums. Store each block's minimum, combine with min, and the same code answers "smallest value from index 2 to 6". Any combine step works if blocks can be merged in any grouping: sum, min, max, greatest common divisor.

Fenwick trees: the compact version

If you only need sums, a Fenwick tree (or binary indexed tree) does the same job with one array of n + 1 numbers and two tiny loops. Each slot stores part of a running total.

The slots are numbered from 1. Slot i stores the sum of the last lowbit(i) items up to item i, where lowbit(i) is the value of the lowest 1 bit of i, written i & -i (see Bit Manipulation). Slot 6 is 110 in binary, its lowest bit is 2, so it holds items 5 and 6. Slot 7 holds one item. Slot 8 holds all eight.

Each Fenwick slot covers a block ending at its own position. To total the first 7 items, add slots 7, 6 and 4.

Two moves do everything:

Total of the first i items: add slot i, then jump to i − lowbit(i), the end of the next block to the left. Repeat until 0. For 7: slots 7, 6, 4.
Add to item i: add to slot i, then jump to i + lowbit(i), the next bigger block that also covers item i. Repeat while inside the array. For item 3: slots 3, 4, 8.

Each jump removes or carries a 1 bit, so either loop runs at most about log₂(n) times. Here is the same correction as before, item 3 (index 2) going up by 5, followed by a query.

Fenwick tree: add 5 to item 3, then total the first 7Use the arrows or ← → keys

add(i, delta): while i <= n: t[i] += delta; i += i & -ifirst(i): s = 0; while i > 0: s += t[i]; i -= i & -i

t
0
15
27
36
416
51
65
77
830
i
-
1The starting slots for 5, 2, 6, 3, 1, 4, 7, 2. Slot 0 is unused.
t
0
15
27
311i
416
51
65
77
830
i
3
2Add 5 at item 3. Slot 3 covers only item 3: 6 becomes 11. lowbit(3) = 1, so jump to 4.
t
0
15
27
311
421i
51
65
77
830
i
4
3Slot 4 covers items 1 to 4, including item 3: 16 becomes 21. lowbit(4) = 4, so jump to 8.
t
0
15
27
311
421
51
65
77
835i
i
8
4Slot 8 covers everything: 30 becomes 35. The next jump is 16, past the end. Three slots changed.
t
0
15
27
311
421
51
65
77i
835
i
7
s
7
5Now total the first 7 items. Start at slot 7 (item 7 alone): s = 7. lowbit(7) = 1, jump to 6.
t
0
15
27
311
421
51
65i
77
835
i
6
s
12
6Slot 6 holds items 5 and 6: s = 7 + 5 = 12. lowbit(6) = 2, jump to 4.
t
0i
15
27
311
421
51
65
77
835
i
0
s
33
7Slot 4 holds items 1 to 4: s = 12 + 21 = 33. lowbit(4) = 4, jump to 0 and stop. Check: 5 + 2 + 11 + 3 + 1 + 4 + 7 = 33.

1 / 7

The code below takes 0-based indexes from the caller and shifts by one inside, so it reads like the prefix sums formula: the sum of left..right is first(right + 1) − first(left).

Fenwick tree

class Fenwick {
  constructor(n) { this.t = new Array(n + 1).fill(0); }
  add(index, delta) { // values[index] += delta
    for (let i = index + 1; i < this.t.length; i += i & -i) this.t[i] += delta;
  }
  first(count) { // sum of the first count values
    let s = 0;
    for (let i = count; i > 0; i -= i & -i) s += this.t[i];
    return s;
  }
  rangeSum(left, right) { return this.first(right + 1) - this.first(left); }
}
 
const fw = new Fenwick(8);
[5, 2, 6, 3, 1, 4, 7, 2].forEach((v, i) => fw.add(i, v));
fw.add(2, 5);
fw.first(7);       // 33
fw.rangeSum(2, 6); // 26

class Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)
 
    def add(self, index, delta):  # values[index] += delta
        i = index + 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & -i
 
    def first(self, count):  # sum of the first count values
        s, i = 0, count
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s
 
    def range_sum(self, left, right):
        return self.first(right + 1) - self.first(left)
 
fw = Fenwick(8)
for i, v in enumerate([5, 2, 6, 3, 1, 4, 7, 2]):
    fw.add(i, v)
fw.add(2, 5)
fw.first(7)        # 33
fw.range_sum(2, 6) # 26

Approach	Time	Space	Why
Plain array	O(1) update, O(n) query	O(1)	Every sum is a loop.
Prefix sums	O(n) update, O(1) query	O(n)	A change shifts every later total.
Segment tree	O(log n) both	O(n)	One node per level on update; at most two partial nodes per level on query. Build is O(n).
Fenwick tree	O(log n) both	O(n)	Each loop step strips or carries one bit. Building by n adds is O(n log n).

To choose, use a Fenwick tree for sums and counts: less code, less memory. Use a segment tree when the combine step is min, max or anything that cannot be undone by subtraction, since the Fenwick range trick relies on subtracting two prefixes.

Common mistakes

Check yourself

Quick check

In a segment tree over 1,000,000 values, about how many nodes change when you update one value?

Which Fenwick slots does the query "total of the first 6 items" read?

You need the smallest value in any range, and values keep changing. Which structure fits?

What to practise next

Change the segment tree code to answer range minimums, and check it on the café numbers by hand. Then read Designing Data Structures, which shows how to combine simple structures into one that meets several targets at once.

#The idea: precompute sums of blocks

#Answering a range query

#Changing one value

#Fenwick trees: the compact version

#Common mistakes

#Check yourself

#What to practise next

The idea: precompute sums of blocks

Answering a range query

Changing one value

Fenwick trees: the compact version

Common mistakes

Check yourself

What to practise next