AdvancedData Structures & Algorithms · Lesson 36 of 40 · Updated ·
Segment Tree and Fenwick Tree — Range Queries with Updates
In the prefix sums lesson we answered "what is the sum of a[L..R]?" in O(1) after an O(n) setup. That works only while the array never changes. Now imagine a placement-test leaderboard: marks change whenever a student submits again, and the website keeps asking for the total marks of students ranked 20 to 60. If one value changes, every prefix sum after it changes too, so each update costs O(n). This lesson shows two structures that make both operations O(log n).
1. The trade-off
| Method | Update one value | Sum of a range |
|---|---|---|
| Plain array | O(1) | O(n) — add them up |
| Prefix sum array | O(n) — rebuild the rest | O(1) |
| Segment tree | O(log n) | O(log n) |
| Fenwick tree (BIT) | O(log n) | O(log n) |
With n = 10⁵ values and 10⁵ mixed updates and queries, the first two rows need on the order of 10¹⁰ steps in the worst case. The last two need a few million.
2. Segment tree: the idea
A segment tree is a binary tree where every node stores the answer (here, the sum) for one segment (a continuous range) of the array:
- the root covers the whole array
[0..n − 1]; - a node covering
[lo..hi]has two children: the left half[lo..mid]and the right half[mid + 1..hi]; - the leaves are single elements.
Query sum(L, R): start at the root.
- If the node's range is completely outside
[L..R], return 0. - If it is completely inside, return its stored sum — no need to go deeper.
- Otherwise split: ask both children and add.
In the picture, sum(2, 6) uses only three nodes: [2..3] = 7, [4..5] = 7 and [6..6] = 7, total 21. It can be shown that any range is covered by at most about 2 nodes per level, so a query visits O(log n) nodes.
Update a[i] = x: change the leaf, then fix the sums on the path back up to the root — one node per level, O(log n).
3. Segment tree code
We store the tree in an array like a heap: node k has children 2k and 2k + 1. An array of size 4n is always big enough.
class SegTree:
def __init__(self, a):
self.n = len(a)
self.t = [0] * (4 * self.n)
self._build(a, 1, 0, self.n - 1)
def _build(self, a, k, lo, hi):
if lo == hi:
self.t[k] = a[lo]
return
mid = (lo + hi) // 2
self._build(a, 2 * k, lo, mid)
self._build(a, 2 * k + 1, mid + 1, hi)
self.t[k] = self.t[2 * k] + self.t[2 * k + 1]
def update(self, i, x, k=1, lo=0, hi=None):
if hi is None:
hi = self.n - 1
if lo == hi:
self.t[k] = x
return
mid = (lo + hi) // 2
if i <= mid:
self.update(i, x, 2 * k, lo, mid)
else:
self.update(i, x, 2 * k + 1, mid + 1, hi)
self.t[k] = self.t[2 * k] + self.t[2 * k + 1]
def query(self, L, R, k=1, lo=0, hi=None):
if hi is None:
hi = self.n - 1
if R < lo or hi < L: # completely outside
return 0
if L <= lo and hi <= R: # completely inside
return self.t[k]
mid = (lo + hi) // 2
return self.query(L, R, 2 * k, lo, mid) + self.query(L, R, 2 * k + 1, mid + 1, hi)
st = SegTree([5, 2, 6, 1, 3, 4, 7, 8])
print(st.query(2, 6), st.query(0, 7))
st.update(3, 10) # a[3]: 1 -> 10
print(st.query(2, 6), st.query(3, 3))
21 36
30 10
Other operations. Change the two + signs and the "outside" value and the same tree answers other questions. For range minimum, combine with min and return infinity for "outside". It works for any operation that can be combined in pieces, such as max, gcd or xor. (For adding a value to a whole range at once there is a further trick called lazy propagation; it is a topic for later practice.)
4. Fenwick tree (binary indexed tree)
A Fenwick tree, also called a binary indexed tree (BIT), does sums with far less code. It uses 1-based indexes and one array T. The trick is the lowest set bit of i, written i & −i:
T[i]stores the sum of the lasti & −ielements ending ati.- For example, 6 is
110in binary, its lowest set bit is 2, soT[6] = a[5] + a[6]. 8 is1000, soT[8]covers all ofa[1..8].
- Prefix sum up to i: add
T[i], then jumpi −= i & −i, untiliis 0. For 7: T[7] + T[6] + T[4]. - Add x at position i: add
xtoT[i], then jumpi += i & −i, until pastn. Every block that contains positionigets updated. - Range sum L..R =
prefix(R) − prefix(L − 1), exactly like prefix sums.
Each jump removes or adds one bit, so both loops run at most about log₂ n times.
public class Main {
static long[] T;
static int n;
static void add(int i, long x) { // a[i] += x (1-based)
for (; i <= n; i += i & -i) T[i] += x;
}
static long prefix(int i) { // a[1] + ... + a[i]
long s = 0;
for (; i > 0; i -= i & -i) s += T[i];
return s;
}
static long rangeSum(int l, int r) {
return prefix(r) - prefix(l - 1);
}
public static void main(String[] args) {
int[] a = {5, 2, 6, 1, 3, 4, 7, 8};
n = a.length;
T = new long[n + 1];
for (int i = 0; i < n; i++) add(i + 1, a[i]);
System.out.println(prefix(7)); // 5+2+6+1+3+4+7
System.out.println(rangeSum(3, 7)); // same range as [2..6] 0-based
add(4, 9); // a[4] goes from 1 to 10
System.out.println(rangeSum(3, 7));
System.out.println(6 & -6);
}
}
28
21
30
2
Note that a Fenwick tree adds to a position. To set a[i] = x, keep a copy of the array and add x − a[i].
5. Which one to use?
| Segment tree | Fenwick tree | |
|---|---|---|
| Code length | longer | very short |
| Memory | about 4n | n + 1 |
| Sum, count | yes | yes |
| Min / max over any range | yes | not directly |
| Range updates | with lazy propagation | with a second tree (advanced) |
A good rule: for sums and counts, write a Fenwick tree. For min, max or anything more unusual, write a segment tree. If the array never changes, plain prefix sums are still the simplest answer.
Common mistakes
- Using a segment tree when no updates happen — prefix sums are enough.
- Making the tree array only
2nlong for the recursive version; use4n. - Returning 0 for "outside" in a min tree; it must be infinity, or every minimum becomes 0.
- Using index 0 in a Fenwick tree:
0 & −0is 0, so the loop never moves. Fenwick trees are 1-based. - Calling
add(i, x)when you meant "set to x"; add the difference instead.
Quick recap
- Prefix sums: fast queries, slow updates. Segment and Fenwick trees: both O(log n).
- Segment tree node = answer for a range; query: outside → 0, inside → stored value, else split.
- Update a leaf, then fix the sums on the way up.
- Fenwick:
T[i]coversi & −iitems; prefix usesi −= i & −i, add usesi += i & −i. - Fenwick for sums, segment tree for min/max and other operations.