PK

PKBytes

Explore tracks
Chapter 29: Fenwick Trees and Segment Trees
29.02Intermediate / Advanced5 topics15 min4 interactive animations

Fenwick variants

Fenwick trees adapted: range updates with point or range queries, frequency counting, finding the k-th element by binary descent, and the 2D version.

Learning goals

  • Support range add and point query with a Fenwick tree over differences
  • Support range add and range sum with two Fenwick trees
  • Count smaller elements and inversions with frequency counts
  • Find the k-th smallest element by descending the tree, and use a 2D tree

Prerequisites

Fenwick treeDifference arraysCoordinate compression

A single Fenwick tree adds one number at one place. With a small change of what the cells mean, the same few lines handle updates over whole ranges, counting, ranking and even rectangles.

29.02.1

Range update/point query

A range add a[l..r] += v is two point changes on the difference array: add v at l and subtract v at r + 1. The value at i is then the prefix sum of the differences up to i. So keep a Fenwick tree over the differences: a range update is two point updates and a point query is one prefix query, each in O(log n).

Try the preset "Range add, point query" (+1:3:5 ?2 ?4 on 1 2 3 4 5 6): the tree cells for positions 2 and 5 change, and the animation reads position 3 as 8 (= 3 + 5) and position 5 as 5 (the add stopped after position 4, so no change). If r + 1 > n, there is nothing to cancel and the second update is skipped.

Java
1class RangeAddPointQuery {
2    private final long[] d;                      // Fenwick tree over the difference array
3    private final int n;
4    RangeAddPointQuery(int n) { this.n = n; d = new long[n + 2]; }
5    private void add(int i, long v) { for (; i <= n; i += i & -i) d[i] += v; }
6    void rangeAdd(int l, int r, long v) {        // 1-based, inclusive
7        add(l, v);
8        add(r + 1, -v);                          // no effect when r + 1 > n
9    }
10    long get(int i) {                            // the sum of the differences up to i
11        long s = 0;
12        for (; i > 0; i -= i & -i) s += d[i];
13        return s;
14    }
15}

Fenwick variants: range update, order statistics, 2D

Interactive · edit the input

Your input

Try

current a[i]

1i=1
2i=2
3i=3
4i=4
5i=5
6i=6

difference BIT d[i]

01: 1..1
02: 1..2
03: 3..3
04: 1..4
05: 5..5
06: 5..6
Setup

A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.

Step 1 / 6
Java
1void rangeAdd(int l, int r, int v) { update(l, v); update(r + 1, -v); }    // d = difference array in a BIT
2int pointQuery(int i) { return a[i] + prefix(i); }                          // a[i] plus all adds that cover i
3void rangeAdd2(int l, int r, int v) {                // two BITs b1, b2
4    update(b1, l, v);      update(b1, r + 1, -v);
5    update(b2, l, v * (l - 1));  update(b2, r + 1, -v * r);
6}
7long prefix2(int i) { return (long) sum(b1, i) * i - sum(b2, i); }        // sum of a[1..i] added so far
8long rangeSum(int l, int r) { return prefix2(r) - prefix2(l - 1); }
9int kth(int k) {                                     // k-th smallest of a multiset of values 1..n kept as frequencies
10    int pos = 0;
11    for (int pw = Integer.highestOneBit(n); pw > 0; pw >>= 1)
12        if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }   // skip a whole block of smaller values
13    return pos + 1;
14}
15void update(int r, int c, int v) {                   // 2D: a BIT of BITs
16    for (int i = r; i <= R; i += i & -i)
17        for (int j = c; j <= C; j += j & -j) bit[i][j] += v;
18}
19int prefix(int r, int c) {
20    int s = 0;
21    for (int i = r; i > 0; i -= i & -i)
22        for (int j = c; j > 0; j -= j & -j) s += bit[i][j];
23    return s;
24}

Live state

0 cells touched

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L1n=6A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.
2L1op=+1:3:5 l=2 v=5 cells changed=[2, 4]+1:3:5: update(2, +5) changes bit cells [2, 4].
3L1op=+1:3:5 r + 1=5 v=-5 cells changed=[5, 6]+1:3:5: update(5, -5) changes bit cells [5, 6]: the add stops after position 4.
4L2op=?2 i=3 a[i]=3 prefix(i) of d=5 return=8?2: prefix(3) of d reads cells [3, 2] = 5; the value is a[3] + 5 = 8.
5L2op=?4 i=5 a[i]=5 prefix(i) of d=0 return=5?4: prefix(5) of d reads cells [5, 4] = 0; the value is a[5] + 0 = 5.
6L2return=[1, 7, 8, 9, 5, 6] cells touched=8Final values [1, 7, 8, 9, 5, 6] (?4 = 5). Both operations are O(log n); with a plain Fenwick tree a range add alone would cost O(n log n).
29.02.2

Range update/range query

To also ask range sums after range adds, one tree is not enough. Let d be the difference array. The prefix sum of the original values after the updates is sum(i) = i × Σ d[1..i] - Σ (j - 1) × d[j] for j ≤ i. Each of the two sums is a Fenwick prefix query, so keep two trees: b1 over d[j] and b2 over d[j] × (j - 1). A range add changes both at l and r + 1.

Why does this work? A single +v at position p in the difference array adds v to every element from p onward, so the prefix sum up to i grows by v × (i - p + 1) when i ≥ p. That equals v × i - v × (p - 1): the first part is b1's contribution times i, the second is b2's. Run the preset "Range add, range sum": after +1:3:5 the sum of positions 1 to 5 of 1 2 3 4 5 6 is 30 (1 + 7 + 8 + 9 + 5).

Java
1class RangeAddRangeSum {
2    private final long[] b1, b2;
3    private final int n;
4    RangeAddRangeSum(int n) { this.n = n; b1 = new long[n + 2]; b2 = new long[n + 2]; }
5    private static void add(long[] b, int n, int i, long v) { for (; i <= n; i += i & -i) b[i] += v; }
6    private static long sum(long[] b, int i) { long s = 0; for (; i > 0; i -= i & -i) s += b[i]; return s; }
7    void rangeAdd(int l, int r, long v) {        // 1-based, inclusive
8        add(b1, n, l, v);            add(b1, n, r + 1, -v);
9        add(b2, n, l, v * (l - 1));  add(b2, n, r + 1, -v * r);
10    }
11    private long prefix(int i) { return sum(b1, i) * i - sum(b2, i); }   // sum of the first i added values
12    long rangeSum(int l, int r) { return prefix(r) - prefix(l - 1); }
13}

Fenwick variants: range update, order statistics, 2D

Interactive · edit the input

Your input

Try

current a[i]

1i=1
2i=2
3i=3
4i=4
5i=5
6i=6

difference BIT d[i]

01: 1..1
02: 1..2
03: 3..3
04: 1..4
05: 5..5
06: 5..6
Setup

A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.

Step 1 / 6
Java
1void rangeAdd(int l, int r, int v) { update(l, v); update(r + 1, -v); }    // d = difference array in a BIT
2int pointQuery(int i) { return a[i] + prefix(i); }                          // a[i] plus all adds that cover i
3void rangeAdd2(int l, int r, int v) {                // two BITs b1, b2
4    update(b1, l, v);      update(b1, r + 1, -v);
5    update(b2, l, v * (l - 1));  update(b2, r + 1, -v * r);
6}
7long prefix2(int i) { return (long) sum(b1, i) * i - sum(b2, i); }        // sum of a[1..i] added so far
8long rangeSum(int l, int r) { return prefix2(r) - prefix2(l - 1); }
9int kth(int k) {                                     // k-th smallest of a multiset of values 1..n kept as frequencies
10    int pos = 0;
11    for (int pw = Integer.highestOneBit(n); pw > 0; pw >>= 1)
12        if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }   // skip a whole block of smaller values
13    return pos + 1;
14}
15void update(int r, int c, int v) {                   // 2D: a BIT of BITs
16    for (int i = r; i <= R; i += i & -i)
17        for (int j = c; j <= C; j += j & -j) bit[i][j] += v;
18}
19int prefix(int r, int c) {
20    int s = 0;
21    for (int i = r; i > 0; i -= i & -i)
22        for (int j = c; j > 0; j -= j & -j) s += bit[i][j];
23    return s;
24}

Live state

0 cells touched

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L1n=6A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.
2L1op=+1:3:5 l=2 v=5 cells changed=[2, 4]+1:3:5: update(2, +5) changes bit cells [2, 4].
3L1op=+1:3:5 r + 1=5 v=-5 cells changed=[5, 6]+1:3:5: update(5, -5) changes bit cells [5, 6]: the add stops after position 4.
4L2op=?2 i=3 a[i]=3 prefix(i) of d=5 return=8?2: prefix(3) of d reads cells [3, 2] = 5; the value is a[3] + 5 = 8.
5L2op=?4 i=5 a[i]=5 prefix(i) of d=0 return=5?4: prefix(5) of d reads cells [5, 4] = 0; the value is a[5] + 0 = 5.
6L2return=[1, 7, 8, 9, 5, 6] cells touched=8Final values [1, 7, 8, 9, 5, 6] (?4 = 5). Both operations are O(log n); with a plain Fenwick tree a range add alone would cost O(n log n).
29.02.3

Frequency counting

A Fenwick tree indexed by value rather than by position counts how many values have been seen. Reading from the right, the number of elements strictly smaller than a[i] among those already inserted is a prefix query on the values below a[i]. This solves 'count of smaller numbers after self', and the sum of all those counts is the number of inversions of the array.

Large or negative values are first mapped to ranks 1..m with coordinate compression (sort the distinct values and use binary search), so the tree has m cells whatever the value range. The loop is O(n log n) in total. Insert after querying, so that an element never counts itself.

Java
1static int[] countSmallerToRight(int[] a) {      // out[i] = number of j > i with a[j] < a[i]
2    int[] sorted = Arrays.stream(a).distinct().sorted().toArray();
3    int m = sorted.length;
4    int[] bit = new int[m + 1];
5    int[] out = new int[a.length];
6    for (int i = a.length - 1; i >= 0; i--) {
7        int rank = Arrays.binarySearch(sorted, a[i]) + 1;          // 1-based rank after compression
8        for (int j = rank - 1; j > 0; j -= j & -j) out[i] += bit[j];   // values strictly smaller
9        for (int j = rank; j <= m; j += j & -j) bit[j]++;              // now count this value
10    }
11    return out;
12}
13static long inversions(int[] a) {                // pairs i < j with a[i] > a[j]
14    long total = 0;
15    for (int c : countSmallerToRight(a)) total += c;
16    return total;
17}
29.02.4

Order statistics

To find the k-th smallest element of a multiset of values 1..n kept as frequencies, you could binary search on the prefix count, costing O(log² n). A Fenwick tree does it in one descent. Start at position 0 and try the powers of two from the highest down: if the block bit[pos + pw] holds fewer than k elements, they are all too small, so skip them (pos += pw, k -= bit[pos]). When the loop ends, pos + 1 is the answer.

Open the preset "k-th smallest": the multiset 5 2 7 2 4 8 is stored as counts of the values 1..8, and the animation descends with pw = 8, 4, 2, 1 to find the 4th smallest, 5. The descent works because each jump lands on a cell that covers exactly the block you skip.

Java
1class FrequencyTree {
2    private final int[] bit;
3    private final int n;
4    FrequencyTree(int n) { this.n = n; bit = new int[n + 1]; }            // values are 1..n
5    void add(int value, int delta) { for (int i = value; i <= n; i += i & -i) bit[i] += delta; }
6    int countAtMost(int value) { int s = 0; for (int i = value; i > 0; i -= i & -i) s += bit[i]; return s; }
7    int kth(int k) {                             // k-th smallest, 1 <= k <= total count
8        int pos = 0;
9        for (int pw = Integer.highestOneBit(n); pw > 0; pw >>= 1) {
10            if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }   // skip a block of smaller values
11        }
12        return pos + 1;
13    }
14}

Fenwick variants: range update, order statistics, 2D

Interactive · edit the input

Your input

Try

current a[i]

1i=1
2i=2
3i=3
4i=4
5i=5
6i=6

difference BIT d[i]

01: 1..1
02: 1..2
03: 3..3
04: 1..4
05: 5..5
06: 5..6
Setup

A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.

Step 1 / 6
Java
1void rangeAdd(int l, int r, int v) { update(l, v); update(r + 1, -v); }    // d = difference array in a BIT
2int pointQuery(int i) { return a[i] + prefix(i); }                          // a[i] plus all adds that cover i
3void rangeAdd2(int l, int r, int v) {                // two BITs b1, b2
4    update(b1, l, v);      update(b1, r + 1, -v);
5    update(b2, l, v * (l - 1));  update(b2, r + 1, -v * r);
6}
7long prefix2(int i) { return (long) sum(b1, i) * i - sum(b2, i); }        // sum of a[1..i] added so far
8long rangeSum(int l, int r) { return prefix2(r) - prefix2(l - 1); }
9int kth(int k) {                                     // k-th smallest of a multiset of values 1..n kept as frequencies
10    int pos = 0;
11    for (int pw = Integer.highestOneBit(n); pw > 0; pw >>= 1)
12        if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }   // skip a whole block of smaller values
13    return pos + 1;
14}
15void update(int r, int c, int v) {                   // 2D: a BIT of BITs
16    for (int i = r; i <= R; i += i & -i)
17        for (int j = c; j <= C; j += j & -j) bit[i][j] += v;
18}
19int prefix(int r, int c) {
20    int s = 0;
21    for (int i = r; i > 0; i -= i & -i)
22        for (int j = c; j > 0; j -= j & -j) s += bit[i][j];
23    return s;
24}

Live state

0 cells touched

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L1n=6A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.
2L1op=+1:3:5 l=2 v=5 cells changed=[2, 4]+1:3:5: update(2, +5) changes bit cells [2, 4].
3L1op=+1:3:5 r + 1=5 v=-5 cells changed=[5, 6]+1:3:5: update(5, -5) changes bit cells [5, 6]: the add stops after position 4.
4L2op=?2 i=3 a[i]=3 prefix(i) of d=5 return=8?2: prefix(3) of d reads cells [3, 2] = 5; the value is a[3] + 5 = 8.
5L2op=?4 i=5 a[i]=5 prefix(i) of d=0 return=5?4: prefix(5) of d reads cells [5, 4] = 0; the value is a[5] + 0 = 5.
6L2return=[1, 7, 8, 9, 5, 6] cells touched=8Final values [1, 7, 8, 9, 5, 6] (?4 = 5). Both operations are O(log n); with a plain Fenwick tree a range add alone would cost O(n log n).
29.02.5

2D BIT

A 2D Fenwick tree is a Fenwick tree of Fenwick trees: cell [i][j] covers lowbit(i) rows by lowbit(j) columns ending at (i, j). An update climbs the row index and, for each row cell, climbs the column index; a prefix query descends both. The cost is O(log R × log C) per operation, with R × C memory.

A rectangle sum uses inclusion-exclusion on four prefix rectangles. In the preset "2D prefix sum" a 3 × 3 grid holds 1..9, and the prefix to row 2, column 3 is 21 (1 + 2 + 3 + 4 + 5 + 6): the animation reads only 2 cells of the bit grid, shown on top.

Java
1class Fenwick2D {
2    private final long[][] bit;
3    private final int rows, cols;
4    Fenwick2D(int rows, int cols) { this.rows = rows; this.cols = cols; bit = new long[rows + 1][cols + 1]; }
5    void update(int r, int c, long v) {          // 1-based
6        for (int i = r; i <= rows; i += i & -i)
7            for (int j = c; j <= cols; j += j & -j) bit[i][j] += v;
8    }
9    long prefix(int r, int c) {                  // sum of the rectangle (1,1)..(r,c)
10        long s = 0;
11        for (int i = r; i > 0; i -= i & -i)
12            for (int j = c; j > 0; j -= j & -j) s += bit[i][j];
13        return s;
14    }
15    long rect(int r1, int c1, int r2, int c2) {  // inclusion-exclusion, inclusive corners
16        return prefix(r2, c2) - prefix(r1 - 1, c2) - prefix(r2, c1 - 1) + prefix(r1 - 1, c1 - 1);
17    }
18}

Fenwick variants: range update, order statistics, 2D

Interactive · edit the input

Your input

Try

current a[i]

1i=1
2i=2
3i=3
4i=4
5i=5
6i=6

difference BIT d[i]

01: 1..1
02: 1..2
03: 3..3
04: 1..4
05: 5..5
06: 5..6
Setup

A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.

Step 1 / 6
Java
1void rangeAdd(int l, int r, int v) { update(l, v); update(r + 1, -v); }    // d = difference array in a BIT
2int pointQuery(int i) { return a[i] + prefix(i); }                          // a[i] plus all adds that cover i
3void rangeAdd2(int l, int r, int v) {                // two BITs b1, b2
4    update(b1, l, v);      update(b1, r + 1, -v);
5    update(b2, l, v * (l - 1));  update(b2, r + 1, -v * r);
6}
7long prefix2(int i) { return (long) sum(b1, i) * i - sum(b2, i); }        // sum of a[1..i] added so far
8long rangeSum(int l, int r) { return prefix2(r) - prefix2(l - 1); }
9int kth(int k) {                                     // k-th smallest of a multiset of values 1..n kept as frequencies
10    int pos = 0;
11    for (int pw = Integer.highestOneBit(n); pw > 0; pw >>= 1)
12        if (pos + pw <= n && bit[pos + pw] < k) { pos += pw; k -= bit[pos]; }   // skip a whole block of smaller values
13    return pos + 1;
14}
15void update(int r, int c, int v) {                   // 2D: a BIT of BITs
16    for (int i = r; i <= R; i += i & -i)
17        for (int j = c; j <= C; j += j & -j) bit[i][j] += v;
18}
19int prefix(int r, int c) {
20    int s = 0;
21    for (int i = r; i > 0; i -= i & -i)
22        for (int j = c; j > 0; j -= j & -j) s += bit[i][j];
23    return s;
24}

Live state

0 cells touched

n

6

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L1n=6A range add [l, r] += v is a pair of point updates on the difference array: +v at l and -v at r + 1. The Fenwick tree d stores that difference array, so the value at i is a[i] plus prefix(i) of d.
2L1op=+1:3:5 l=2 v=5 cells changed=[2, 4]+1:3:5: update(2, +5) changes bit cells [2, 4].
3L1op=+1:3:5 r + 1=5 v=-5 cells changed=[5, 6]+1:3:5: update(5, -5) changes bit cells [5, 6]: the add stops after position 4.
4L2op=?2 i=3 a[i]=3 prefix(i) of d=5 return=8?2: prefix(3) of d reads cells [3, 2] = 5; the value is a[3] + 5 = 8.
5L2op=?4 i=5 a[i]=5 prefix(i) of d=0 return=5?4: prefix(5) of d reads cells [5, 4] = 0; the value is a[5] + 0 = 5.
6L2return=[1, 7, 8, 9, 5, 6] cells touched=8Final values [1, 7, 8, 9, 5, 6] (?4 = 5). Both operations are O(log n); with a plain Fenwick tree a range add alone would cost O(n log n).

Practice ladder

Now try it yourself

Easy

  • Range Sum Query - Mutable

Medium

  • Count of Smaller Numbers After Self
  • Range Sum Query 2D - Mutable
  • Range Frequency Queries

Advanced

  • Reverse Pairs
  • Count of Range Sum
  • Create Sorted Array through Instructions

Key takeaways

  • Range add + point query: a Fenwick tree over the difference array.
  • Range add + range sum: two trees, b1 over d[j] and b2 over d[j] × (j - 1); sum(i) = i × Σb1 - Σb2.
  • Index the tree by value to count and rank; descend by powers of two to find the k-th element; add a second index for 2D.