Segment Trees and Fenwick Trees· 25 min

Segment Tree (Range Sum)

Answer any range query in O(log n) with a sum tree

Setup

Step 1 / 20

Current step

1 / 20

Build a segment tree over [5, 8, 6, 3, 2, 7, 2, 6] — an array of 16 slots: leaves at 8..15, parents above.

Step log

5
0
8
1
6
2
3
3
2
4
7
5
2
6
6
7
Touching now
Contributing to answer
Not built yet
segment_tree.java
1public class Main {
2    private final int size;
3    private final int[] tree;
4 
5    public Main(int[] values) {
6        size = values.length;
7        tree = new int[2 * size];
8        System.arraycopy(values, 0, tree, size, size);
9        for (int i = size - 1; i > 0; i--) tree[i] = tree[2 * i] + tree[2 * i + 1];
10    }
11 
12    public int rangeSum(int left, int right) {
13        int sum = 0;
14        for (left += size, right += size; left < right; left /= 2, right /= 2) {
15            if ((left & 1) == 1) sum += tree[left++];
16            if ((right & 1) == 1) sum += tree[--right];
17        }
18        return sum;
19    }
20 
21}
● Java
Query
O(log n)
Update
O(log n)
Build
O(n)
Space
O(2n)
43 / 46