Skills101

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

MethodUpdate one valueSum of a range
Plain arrayO(1)O(n) — add them up
Prefix sum arrayO(n) — rebuild the restO(1)
Segment treeO(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.

Segment tree of sums for the array 5 2 6 1 3 4 7 8: the root holds 36, the leaves hold the array values, and the green nodes for 2..3, 4..5 and 6..6 together cover the query range 2 to 6 with sum 21

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 last i & −i elements ending at i.
  • For example, 6 is 110 in binary, its lowest set bit is 2, so T[6] = a[5] + a[6]. 8 is 1000, so T[8] covers all of a[1..8].

Fenwick tree ranges for indexes 1 to 8: entries 1, 3, 5 and 7 cover one item, entries 2 and 6 cover two, entry 4 covers four and entry 8 covers all eight; prefix(7) adds entries 7, 6 and 4

  • Prefix sum up to i: add T[i], then jump i −= i & −i, until i is 0. For 7: T[7] + T[6] + T[4].
  • Add x at position i: add x to T[i], then jump i += i & −i, until past n. Every block that contains position i gets 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 treeFenwick tree
Code lengthlongervery short
Memoryabout 4nn + 1
Sum, countyesyes
Min / max over any rangeyesnot directly
Range updateswith lazy propagationwith 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 2n long for the recursive version; use 4n.
  • 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 & −0 is 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] covers i & −i items; prefix uses i −= i & −i, add uses i += i & −i.
  • Fenwick for sums, segment tree for min/max and other operations.

Practice what you learned

📝 Quiz: Segment Tree and Fenwick Tree5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →