Segment Trees and Fenwick Trees· 20 min

Fenwick Tree (BIT)

Prefix sums via the lowest-set-bit trick

Setup

Step 1 / 13

Current step

1 / 13

A Fenwick tree stores partial sums in an array. bit[i] covers the last (i & -i) elements ending at i.

Step log

Original array
5
0
8
1
6
2
3
3
2
4
7
5
2
6
6
7
Fenwick array (1-indexed) — sublabel shows how many elements each slot covers
0±1
1
0±2
2
0±1
3
0±4
4
0±1
5
0±2
6
0±1
7
0±8
8
Touching now
Contributing to answer
fenwick_tree.java
1public class Main {
2    private final int[] bit;
3 
4    public Main(int size) {
5        bit = new int[size + 1];
6    }
7 
8    public void update(int index, int delta) {
9        for (; index < bit.length; index += index & -index) bit[index] += delta;
10    }
11 
12    public int prefixSum(int index) {
13        int sum = 0;
14        for (; index > 0; index -= index & -index) sum += bit[index];
15        return sum;
16    }
17 
18}
● Java
Query
O(log n)
Update
O(log n)
Build
O(n)
Space
O(n)
44 / 46