Segment trees and Fenwick trees

Introduction

A shop records its sales for every day. Two things happen again and again: "what were the total sales from day l to day r?" and "day i's figure was wrong: change it". With n days:

When both kinds of operation are frequent, the tree wins: a million operations on a million days take about 20 million steps instead of a million million.

Precomputing answers makes questions fast, until the data changes and all that work must be redone. A segment tree stores just enough partial answers that one change repairs only a few of them.

How it works

Fenwick trees: the short version

A Fenwick tree (binary indexed tree) does prefix sums and single updates in O(log n) with ten lines of code. It is 1-based, and i & -i is the lowest set bit of i (see the Bit manipulation lesson):

#include <stdio.h>

#define N 8
int bit[N + 1];                       // 1-based: bit[0] is not used

void add(int i, int delta) {          // a[i] += delta
    for (; i <= N; i += i & -i) bit[i] += delta;
}

int prefix(int i) {                   // a[1] + ... + a[i]
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

int main(void) {
    int a[N + 1] = {0, 5, 8, 6, 3, 2, 7, 2, 6};
    for (int i = 1; i <= N; i++) add(i, a[i]);
    printf("sum of a[3..7] = %d\n", prefix(7) - prefix(2));
    add(4, 6);                        // a[4]: 3 becomes 9
    printf("after the change: %d\n", prefix(7) - prefix(2));
    return 0;
}

bit[i] holds the sum of the i & -i values ending at position i. prefix jumps down by removing the lowest bit; add jumps up by adding it. A range sum is prefix(r) - prefix(l - 1).

Which one?

• Fenwick tree: sums (and anything you can subtract), shortest code, smallest memory.
• Segment tree: also minimum, maximum, GCD, or "the first value bigger than x". Minimum cannot be "subtracted", so prefix tricks fail; a segment tree only needs to combine two halves.
• With lazy propagation, a segment tree can also add a value to a whole range in O(log n): a topic for competitive programming.

Syntax

int tree[4 * N];

// node k has children 2k and 2k + 1
tree[node] = tree[2 * node] + tree[2 * node + 1];

Example

A segment tree is a binary tree over the array. The root stores the sum of the whole array; its two children store the sums of the left and right halves; their children the quarters, and so on down to single values. Like a heap, it lives in an array: node k has children 2k and 2k + 1, starting from node 1. An array of 4n entries is always big enough.

#include <stdio.h>

#define N 8
int a[N] = {5, 8, 6, 3, 2, 7, 2, 6};
int tree[4 * N];

void build(int node, int lo, int hi) {
    if (lo == hi) {
        tree[node] = a[lo];
        return;
    }
    int mid = (lo + hi) / 2;
    build(2 * node, lo, mid);
    build(2 * node + 1, mid + 1, hi);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;              // outside: adds nothing
    if (l <= lo && hi <= r) return tree[node];   // fully inside: use it whole
    int mid = (lo + hi) / 2;                     // partly inside: ask both halves
    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
}

void update(int node, int lo, int hi, int i, int value) {
    if (lo == hi) {
        tree[node] = value;
        return;
    }
    int mid = (lo + hi) / 2;
    if (i <= mid) update(2 * node, lo, mid, i, value);
    else update(2 * node + 1, mid + 1, hi, i, value);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int main(void) {
    build(1, 0, N - 1);
    printf("sum of a[2..6] = %d\n", query(1, 0, N - 1, 2, 6));
    update(1, 0, N - 1, 3, 9);
    printf("after a[3] = 9: %d\n", query(1, 0, N - 1, 2, 6));
    return 0;
}

Building fills the leaves, then each parent as the sum of its two children: O(n).

A query for a[l..r] starts at the root and, at each node, asks how its range meets [l, r]:

• outside: return 0 and stop;
• fully inside: return the stored sum and stop, without looking below;
• partly inside: ask both children and add their answers.

At most four nodes per level are visited, so a query is O(log n). Try it in the DSA Lab's Segment tree tool and watch which nodes are used whole.

An update walks down to the leaf, changes it, and fixes the sums on the way back up: one node per level, O(log n).

Line by line

1. tree has room for 4 * N nodes, and node 1 is the root covering the whole array.
2. build fills in a leaf when the range has one position. Otherwise it builds both halves and adds them.
3. query returns 0 for a range wholly outside the question, and the stored sum for one wholly inside.
4. For a range that is partly inside, it asks both halves and adds the answers.
5. update walks down to the one leaf, changes it, and recomputes each sum on the way back.
6. main builds the tree, asks for the sum of positions 2 to 6, changes position 3 to 9, and asks again.

Expected result

sum of a[2..6] = 20
after a[3] = 9: 26

In the real world

Games and financial systems use these trees for questions such as "what is the highest score in this range?" while new scores keep arriving. They are also a staple of programming contests.

Common mistakes

• An array of 2n nodes: when n is not a power of two, node numbers go past 2n. Use 4n.
• Mixing up inclusive and exclusive ends: decide that [l, r] includes both ends, and keep to it.
• Calling a Fenwick tree with index 0: 0 & -0 is 0, so the loop never moves. Shift to 1-based indexes.

Best practices

• Decide that a range includes both ends, and keep to that everywhere.
• Allocate 4 * N nodes rather than trying to compute the exact number.
• Choose a Fenwick tree when sums are all you need.

Summary

A segment tree stores the summary of each half, quarter and so on, so a query combines O(log n) stored answers and an update repairs one path. A Fenwick tree does prefix sums in far less code.

Mark lesson complete