AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content

10 Segment trees and Fenwick trees / Lesson 1 of 1

Segment trees and Fenwick trees

15 min · +10 XP · 2 exercises · 4 questions

Read the text15 min
Exercises0/2
Quiz4 q

Quick answer

What is a segment tree?

A segment tree is a binary tree over an array in which every node stores the answer for one contiguous range — a sum, minimum or maximum — with the root covering the whole array and the leaves single elements. A point update rewrites one leaf and its O(log n) ancestors, and a range query combines at most about 2 log n nodes, so both run in O(log n).

Prefix sums answer a range sum in O(1) — until the array changes. One update rebuilds O(n) of the prefix array, so 2 × 10⁵ updates and queries cost 4 × 10¹⁰ steps. The fix is a structure in which an update and a query are both O(log n).

A segment tree: one node per range

  • The root covers the whole array; each node splits its range in half between two children; the leaves are single elements.
  • Every node stores the answer for its range — a sum here, but minimum, maximum and GCD work the same way (any associative operation).
  • One array holds it: node v has children 2v and 2v + 1, and 4n slots is always enough.
A segment tree: a point update climbs, a range query collects
a = [5, 3, 7, 2, 6, 1, 4, 8]

Each node stores the sum of its range. The leaves are a = [5, 3, 7, 2, 6, 1, 4, 8]; each parent adds its two children, and the root holds 36, the whole array.

0:01 / 0:19Step 1 of 7
Transcript · 7 steps
  • Update: change the leaf, then recompute each ancestor from its two children — one node per level, O(log n).
  • Query [l, r]: start at the root. A node fully inside the range gives its value, one fully outside gives the identity (0 for a sum, +∞ for a minimum), and a partial one asks both children. At most four nodes per level are visited.
void update(int v, int lo, int hi, int pos, ll val) {
    if (lo == hi) { t[v] = val; return; }
    int mid = (lo + hi) / 2;
    if (pos <= mid) update(2 * v, lo, mid, pos, val);
    else update(2 * v + 1, mid + 1, hi, pos, val);
    t[v] = t[2 * v] + t[2 * v + 1];
}
ll query(int v, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;            // outside: the identity
    if (l <= lo && hi <= r) return t[v];       // inside: the whole node
    int mid = (lo + hi) / 2;
    return query(2 * v, lo, mid, l, r) + query(2 * v + 1, mid + 1, hi, l, r);
}

A Fenwick tree: prefix sums in ten lines

When the operation can be undone — sums, counts, XOR — a Fenwick (binary indexed) tree is shorter and faster.

  • Cell i (1-indexed) holds the sum of the i & -i elements ending at i. i & -i is the lowest set bit: 6 = 110₂ gives 2, 8 gives 8.
  • add(i, x) climbs i += i & -i, touching every cell whose range covers i.
  • sum(i) descends i -= i & -i, collecting disjoint ranges that tile 1..i. A range is sum(r) − sum(l − 1).
A Fenwick tree: add climbs with i += i & -i, sum descends with i -= i & -i
a = [5, 3, 7, 2, 6, 1, 4, 8] (positions 1..8)

Each cell i covers the i & -i positions ending at i: cell 6 (110 in binary) covers 5..6, cell 8 covers 1..8. Odd cells hold one value; the bars are the tree.

0:01 / 0:17Step 1 of 7
Transcript · 7 steps
struct BIT {
    int n; vector<ll> f;
    BIT(int n) : n(n), f(n + 1, 0) {}
    void add(int i, ll x) { for (; i <= n; i += i & -i) f[i] += x; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += f[i]; return s; }
};

The classic trick is to index the tree by value instead of position. Scanning left to right, "how many earlier elements are greater than x" is seen − sum(rank(x)), which counts inversions in O(n log n). Compress values to ranks 1..m first with sort, unique and lower_bound.

More practice

Common questions

What is the difference between a segment tree and a Fenwick tree?

A Fenwick tree (binary indexed tree) keeps prefix sums in one array of n + 1 values and takes about ten lines; it works for operations that can be undone, such as sums, counts and XOR. A segment tree uses up to 4n nodes and also handles minimum, maximum, GCD and lazy range updates. Both answer in O(log n).

What does i & -i do in a Fenwick tree?

In two's complement, i & -i keeps only the lowest set bit of i. Fenwick cell i stores the sum of the i & -i elements ending at position i, so an update climbs with i += i & -i and a prefix query descends with i -= i & -i, each touching at most about log2 n cells.

How do you count inversions with a Fenwick tree?

Compress the values to ranks 1..m, then scan the array from left to right. Before recording element x, the number of earlier elements greater than x is the count seen so far minus the Fenwick prefix sum up to rank(x). Add that to the answer, then add 1 at rank(x). The whole scan is O(n log n).

When is a prefix-sum array enough instead of a segment tree?

When the array never changes. A prefix-sum array answers each range sum in O(1) after O(n) preparation, but a single point update costs O(n) to rebuild it. Once updates and queries interleave, use an O(log n) structure: at n = q = 2 × 10^5, rebuilding after every update is 4 × 10^10 steps.

Mark as readSign in to keep your place.
AI InterviewGet started

Segment Tree vs Fenwick Tree in C++: Fast Range Queries

A segment tree answers range sum or minimum queries with point updates in O(log n); a Fenwick tree does prefix sums in ten lines with i & -i. Both in C++.

What is a segment tree?

A segment tree is a binary tree over an array in which every node stores the answer for one contiguous range — a sum, minimum or maximum — with the root covering the whole array and the leaves single elements. A point update rewrites one leaf and its O(log n) ancestors, and a range query combines at most about 2 log n nodes, so both run in O(log n).

Lesson

Prefix sums answer a range sum in O(1) — until the array changes. One update rebuilds O(n) of the prefix array, so 2 × 10⁵ updates and queries cost 4 × 10¹⁰ steps. The fix is a structure in which an update and a query are both O(log n).

A segment tree: one node per range

  • The root covers the whole array; each node splits its range in half between two children; the leaves are single elements.
  • Every node stores the answer for its range — a sum here, but minimum, maximum and GCD work the same way (any associative operation).
  • One array holds it: node v has children 2v and 2v + 1, and 4n slots is always enough.
53879162461748121943a0a1a2a3a4a5a6a7sum = 3 + 16 + 7 + 4 = 30
A segment tree: a point update climbs, a range query collects. Example: a = [5, 3, 7, 2, 6, 1, 4, 8]
  1. Each node stores the sum of its range. The leaves are a = [5, 3, 7, 2, 6, 1, 4, 8]; each parent adds its two children, and the root holds 36, the whole array.
  2. Point update a3 = 9: the leaf changes from 2 to 9. Only its ancestors cover position 3, one per level.
  3. Recompute node [2..3] from its children: 7 + 9 = 16.
  4. Recompute node [0..3] from its children: 8 + 16 = 24.
  5. Recompute node [0..7] from its children: 24 + 19 = 43. 4 nodes changed in all — O(log n).
  6. Query sum of a1..a6. The recursion splits the nodes that are only partly inside — [0..7], [0..3], [0..1], [4..7], [6..7] — and stops at nodes fully inside or fully outside.
  7. The whole nodes it collects tile the range exactly: [1] = 3, [2..3] = 16, [4..5] = 7, [6] = 4. Their sum is 30, from 4 nodes instead of 6 leaves.
  • Update: change the leaf, then recompute each ancestor from its two children — one node per level, O(log n).
  • Query [l, r]: start at the root. A node fully inside the range gives its value, one fully outside gives the identity (0 for a sum, +∞ for a minimum), and a partial one asks both children. At most four nodes per level are visited.
void update(int v, int lo, int hi, int pos, ll val) {
    if (lo == hi) { t[v] = val; return; }
    int mid = (lo + hi) / 2;
    if (pos <= mid) update(2 * v, lo, mid, pos, val);
    else update(2 * v + 1, mid + 1, hi, pos, val);
    t[v] = t[2 * v] + t[2 * v + 1];
}
ll query(int v, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;            // outside: the identity
    if (l <= lo && hi <= r) return t[v];       // inside: the whole node
    int mid = (lo + hi) / 2;
    return query(2 * v, lo, mid, l, r) + query(2 * v + 1, mid + 1, hi, l, r);
}

A Fenwick tree: prefix sums in ten lines

When the operation can be undone — sums, counts, XOR — a Fenwick (binary indexed) tree is shorter and faster.

  • Cell i (1-indexed) holds the sum of the i & -i elements ending at i. i & -i is the lowest set bit: 6 = 110₂ gives 2, 8 gives 8.
  • add(i, x) climbs i += i & -i, touching every cell whose range covers i.
  • sum(i) descends i -= i & -i, collecting disjoint ranges that tile 1..i. A range is sum(r) − sum(l − 1).
5f2 = 814f4 = 246f6 = 74f8 = 431000120010300114010050101601107011181000sum(7) = 4 + 7 + 24 = 35
A Fenwick tree: add climbs with i += i & -i, sum descends with i -= i & -i. Example: a = [5, 3, 7, 2, 6, 1, 4, 8] (positions 1..8)
  1. Each cell i covers the i & -i positions ending at i: cell 6 (110 in binary) covers 5..6, cell 8 covers 1..8. Odd cells hold one value; the bars are the tree.
  2. add(3, +7) at i = 3: f3 becomes 7 + 7 = 14. Then i += i & -i = 1 gives 4.
  3. add(3, +7) at i = 4: f4 becomes 17 + 7 = 24. Then i += i & -i = 4 gives 8.
  4. add(3, +7) at i = 8: f8 becomes 36 + 7 = 43. Then i += i & -i = 8 gives 16, past n = 8: done after 3 cells.
  5. sum(7) at i = 7: take f7 = 4, which covers position 7. Then i -= i & -i gives 6.
  6. sum(7) at i = 6: take f6 = 7, which covers 5..6. Then i -= i & -i gives 4.
  7. sum(7) at i = 4: take f4 = 24, which covers 1..4. Then i -= i & -i gives 0: the cells tile 1..7 and the prefix sum is 35.
struct BIT {
    int n; vector<ll> f;
    BIT(int n) : n(n), f(n + 1, 0) {}
    void add(int i, ll x) { for (; i <= n; i += i & -i) f[i] += x; }
    ll sum(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += f[i]; return s; }
};

The classic trick is to index the tree by value instead of position. Scanning left to right, "how many earlier elements are greater than x" is seen − sum(rank(x)), which counts inversions in O(n log n). Compress values to ranks 1..m first with sort, unique and lower_bound.

More practice

Common questions

What is the difference between a segment tree and a Fenwick tree?

A Fenwick tree (binary indexed tree) keeps prefix sums in one array of n + 1 values and takes about ten lines; it works for operations that can be undone, such as sums, counts and XOR. A segment tree uses up to 4n nodes and also handles minimum, maximum, GCD and lazy range updates. Both answer in O(log n).

What does i & -i do in a Fenwick tree?

In two's complement, i & -i keeps only the lowest set bit of i. Fenwick cell i stores the sum of the i & -i elements ending at position i, so an update climbs with i += i & -i and a prefix query descends with i -= i & -i, each touching at most about log2 n cells.

How do you count inversions with a Fenwick tree?

Compress the values to ranks 1..m, then scan the array from left to right. Before recording element x, the number of earlier elements greater than x is the count seen so far minus the Fenwick prefix sum up to rank(x). Add that to the answer, then add 1 at rank(x). The whole scan is O(n log n).

When is a prefix-sum array enough instead of a segment tree?

When the array never changes. A prefix-sum array answers each range sum in O(1) after O(n) preparation, but a single point update costs O(n) to rebuild it. Once updates and queries interleave, use an O(log n) structure: at n = q = 2 × 10^5, rebuilding after every update is 4 × 10^10 steps.

Exercises

Point updates, range sums and minimums

Read an array of n integers and answer q operations, each one of:

  • 1 i v — set a[i] = v;
  • 2 l r — print the sum and the minimum of a[l..r], separated by a space.

Positions are 1-indexed. Build a segment tree that stores both the sum and the minimum of every node's range: each operation in O(log n).

Constraints: 1 ≤ n, q ≤ 2 × 10^5, |a[i]|, |v| ≤ 10^9, 1 ≤ l ≤ r ≤ n. Input: n q, the n values, then q lines. Output: one line per type-2 operation.

5 5
5 3 7 2 6
2 1 5
2 2 4
1 4 9
2 2 4
2 4 4

prints

23 2
12 2
19 3
9 9

Count inversions with a Fenwick tree

Read n integers and print the number of inversions: pairs i < j with a[i] > a[j].

Compress the values to ranks, then scan left to right with a Fenwick tree indexed by rank: before recording a[j], the earlier elements greater than it are j − sum(rank(a[j])). O(n log n) in all.

Constraints: 1 ≤ n ≤ 2 × 10^5, 1 ≤ a[i] ≤ 10^9 (values may repeat; equal values are not an inversion). Input: n, then the values. Output: the count.

5
2 4 1 3 5

prints 3 — the pairs (2, 1), (4, 1) and (4, 3).

In this module: Segment trees and Fenwick trees

← Checkpoint — Topological sort and DAGs · Checkpoint — Segment trees and Fenwick trees →