Fenwick Tree

Fenwick Tree | Algoryva

First, the naive way

A prefix array that must be rebuilt

The Prefix Sum lesson gave O(1) range sums, but only for data that never changes. If one value changes, every prefix sum after it changes too.

Rebuilding the prefix array after each update costs O(n). With n = q = 2 × 10⁵ interleaved updates and queries, that is about 4 × 10¹⁰ steps. Skipping the array and summing the range directly costs O(n) per query: equally slow.

python

from itertools import accumulate

a = [3, 2, -1, 6, 5, 4, -3, 3]
prefix = [0] + list(accumulate(a))
print(prefix[7] - prefix[0])   # 16

a[2] += 5                              # one value changes ...
prefix = [0] + list(accumulate(a))     # ... so the whole prefix array is rebuilt: O(n)
print(prefix[7] - prefix[0])   # 21

Cost: O(n) per update (or O(n) per query), so O(n × q) overall when updates and queries are mixed.

Worked by hand

The numbers by hand

For a = [3, 2, −1, 6, 5, 4, −3, 3] (positions 1 to 8), the stored blocks are:

i	lowbit	block covered	T[i]
1	1	1	3
2	2	1 to 2	5
3	1	3	−1
4	4	1 to 4	10
5	1	5	5
6	2	5 to 6	9
7	1	7	−3
8	8	1 to 8	19

1
Prefix of 7
7 = 111 in binary. Take T[7] = −3 (position 7), then i = 6: T[6] = 9 (positions 5 to 6), then i = 4: T[4] = 10 (positions 1 to 4). Total −3 + 9 + 10 = 16. Three reads instead of seven.
2
Update position 3 by +5
T[3] becomes 4, then i = 3 + 1 = 4: T[4] becomes 15, then i = 4 + 4 = 8: T[8] becomes 24, then i = 16 which is past the end. Three writes.

Implementation

A Fenwick tree in a dozen lines

The class has three methods. The two loops are the two walks.

Plan in plain steps

pseudocode

update(i, δ): while i <= n: T[i] += δ; i += lowbit(i)
prefix(i):    total = 0; while i > 0: total += T[i]; i -= lowbit(i); return total
range_sum(l, r) = prefix(r) − prefix(l − 1)

python

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)          # 1-indexed: t[0] is unused

    def update(self, i, delta):          # add delta to position i
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def prefix(self, i):                 # sum of positions 1..i
        total = 0
        while i > 0:
            total += self.t[i]
            i -= i & -i
        return total

    def range_sum(self, l, r):           # sum of positions l..r
        return self.prefix(r) - self.prefix(l - 1)

f = Fenwick(8)
for i, v in enumerate([3, 2, -1, 6, 5, 4, -3, 3], start=1):
    f.update(i, v)
print(f.prefix(7))   # 16
print(f.range_sum(3, 6))   # 14
f.update(3, 5)
print(f.range_sum(3, 6))   # 19
print(f.t[1:])   # [3, 5, 4, 15, 5, 9, -3, 24]
print(5 & -5, 6 & -6, 8 & -8, 12 & -12)   # 1 2 8 4

Reading the code

›update walks up: from i to the next block that contains it. prefix walks down: from i stripping its lowest bit.
›Building the tree by calling update once per value costs O(n log n). The final print(f.t[1:]) shows the array after the extra update(3, 5): [3, 5, 4, 15, 5, 9, -3, 24], exactly as in the animation.
›range_sum(3, 6) is prefix(6) − prefix(2): from 14 to 19 after adding 5 at position 3.
›The last line shows lowbit for a few numbers: 5 & -5 = 1, 6 & -6 = 2, 8 & -8 = 8, 12 & -12 = 4.

Implementation

Building in O(n), and checking it

Instead of n separate updates, push each block's total into its parent block once. The parent of block i is i + lowbit(i). The second half of the snippet checks the result against plain sums on 300 random arrays, a habit worth copying whenever you write a data structure.

python

def build(a):
    n = len(a)
    t = [0] + list(a)
    for i in range(1, n + 1):
        j = i + (i & -i)                 # the parent block that also contains position i
        if j <= n:
            t[j] += t[i]
    return t

print(build([3, 2, -1, 6, 5, 4, -3, 3])[1:])   # [3, 5, -1, 10, 5, 9, -3, 19]

import random
random.seed(5)
ok = True
for _ in range(300):
    a = [random.randint(-9, 9) for _ in range(random.randint(1, 12))]
    t = build(a)
    for i in range(1, len(a) + 1):
        total, j = 0, i
        while j > 0:
            total += t[j]
            j -= j & -j
        ok = ok and total == sum(a[:i])
print(ok)   # True

Reading the code

›t = [0] + list(a) starts every block as just its own value. Then in increasing i, add t[i] to its parent t[i + lowbit(i)]. By the time we reach i, all of its children have already contributed.
›The result [3, 5, -1, 10, 5, 9, -3, 19] matches the table in the example (before the update).
›The check confirms that for every prefix, the walk over t equals the ordinary sum of the first i values: it prints True.
›Total cost is O(n): each position pushes into one parent.

Worked problem

A mutable array with range sums

The problem

Design a structure for an array of integers that supports set(i, v) (replace the value at index i) and sum(l, r) (the sum of indices l to r, 0-indexed, inclusive), each in O(log n).

Keep a copy of the current values and a Fenwick tree over them.
To set a value, add the difference v − old at position i + 1 (the tree is 1-indexed), then store the new value.
To sum a range, use range_sum(l + 1, r + 1).

python

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)          # 1-indexed: t[0] is unused

    def update(self, i, delta):          # add delta to position i
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def prefix(self, i):                 # sum of positions 1..i
        total = 0
        while i > 0:
            total += self.t[i]
            i -= i & -i
        return total

    def range_sum(self, l, r):           # sum of positions l..r
        return self.prefix(r) - self.prefix(l - 1)

class NumArray:
    def __init__(self, nums):
        self.a = [0] * len(nums)
        self.f = Fenwick(len(nums))
        for i, v in enumerate(nums):
            self.set(i, v)

    def set(self, i, v):                  # i is 0-indexed here
        self.f.update(i + 1, v - self.a[i])
        self.a[i] = v

    def sum(self, l, r):
        return self.f.range_sum(l + 1, r + 1)

na = NumArray([1, 3, 5])
print(na.sum(0, 2))   # 9
na.set(1, 2)
print(na.sum(0, 2))   # 8
na.set(1, 2)
print(na.sum(1, 1))   # 2

Takeaway. Setting a value is the same as adding a difference, which is why a structure built for add also supports set. The only bookkeeping is the 0-indexed to 1-indexed shift. Calling set(1, 2) twice leaves the sum unchanged the second time, because the difference is 0.

Worked problem

Count inversions with a Fenwick tree

The problem

Count the pairs of positions i < j with a[i] > a[j] in O(n log n). (The Sorting II lesson solved this with merge sort.)

Process the array left to right. For each new value x, the inversions it completes are the earlier values strictly greater than x.
Keep a Fenwick tree counting how many earlier values have each rank. The number of earlier values that are *not greater* than x is prefix(rank of x), so the number that are greater is seen − prefix(rank).
Values can be as large as 10⁹, so first map them to ranks 1..k (coordinate compression) by sorting the distinct values.

python

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)          # 1-indexed: t[0] is unused

    def update(self, i, delta):          # add delta to position i
        while i <= self.n:
            self.t[i] += delta
            i += i & -i

    def prefix(self, i):                 # sum of positions 1..i
        total = 0
        while i > 0:
            total += self.t[i]
            i -= i & -i
        return total

    def range_sum(self, l, r):           # sum of positions l..r
        return self.prefix(r) - self.prefix(l - 1)

def count_inversions(a):
    ranks = {v: i for i, v in enumerate(sorted(set(a)), start=1)}   # compress values to 1..k
    f = Fenwick(len(ranks))
    inversions = 0
    for seen, x in enumerate(a):
        r = ranks[x]
        inversions += seen - f.prefix(r)       # earlier values that are strictly greater than x
        f.update(r, 1)
    return inversions

print(count_inversions([2, 4, 1, 3, 5]))   # 3
print(count_inversions([5, 4, 3, 2, 1]))   # 10
print(count_inversions([2, 2, 1]))   # 2
print(count_inversions([10**9, 1, 10**9]))   # 1

Takeaway. A Fenwick tree is a fast way to ask “how many items so far are at most x?” while inserting items one at a time. The same pattern gives “count of smaller numbers after self” and many ordering-count problems. The fourth call shows compression at work: huge values become ranks 2, 1, 2 and the answer is 1.

Wrap-up

Remember this

A Fenwick tree keeps prefix sums current under updates: both a query and an update cost O(log n).
Cell T[i] stores the sum of the lowbit(i) values ending at position i; queries strip the lowest bit, updates add it.
Set a value by adding the difference; build in O(n) by pushing each block into its parent.
It only works for operations that can be undone (sum, xor, count), not min or max.
With coordinate compression it counts inversions and “how many earlier values are at most x”.

Cheat sheet

lowbit: i & -i (lowest set bit)
Update (add δ at i): while i <= n: T[i] += δ; i += i & -i
Prefix (sum of 1..i): while i > 0: total += T[i]; i -= i & -i
Range: prefix(r) − prefix(l − 1)
Cost: O(log n) per operation, O(n) build, O(n) space
Needs: 1-indexing and an invertible operation (sum, xor, count)

Top traps to avoid

Using 0-indexed positions.
Writing i -= i & -i in the update loop (or += in the query loop).
Using it for minimum or maximum range queries.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is 12 & -12, the lowbit of 12?
2.In an 8-position Fenwick tree, which cells does a prefix query for position 7 read?
3.Updating position 3 in an 8-position tree changes which cells?
4.What does a Fenwick tree cost per point update or prefix query?
5.“Handle many updates to single values and many queries for the sum of a range” suggests:
6.Why can a Fenwick tree not answer range-minimum queries the way it answers range sums?
7.Fenwick tree over [1, 2, 3, 4, 5] (1-indexed, built by adding each value). What is the prefix sum q(3)?
8.After adding 10 at position 2 of the same tree, what is q(5)?
9.Same tree with no update: what is the range sum from position 2 to 4 (q(4) - q(1))?
10.What does the trick i & -i (the lowest set bit) give a Fenwick tree?
11.A Fenwick tree update or prefix query on n items: what is the time?
12.Why can't a Fenwick tree directly answer range minimum queries?
13.Count inversions with a Fenwick tree for a = [3, 1, 2] (pairs where a larger value comes first). What is printed?
14.Why are Fenwick trees usually 1-indexed?
15.What does q(0) return on a Fenwick tree with any values added?

Fenwick Tree

After this lesson you will be able to

Builds on

Unlocks

A ledger with running subtotals on every page

A prefix array that must be rebuilt

Blocks whose length is the lowest set bit

lowbit and the two walks

A query and an update on 8 values

The numbers by hand

A Fenwick tree in a dozen lines

Reading the code

Building in O(n), and checking it

Reading the code

Costs, and what a Fenwick tree cannot do

Edge cases

Mistakes to avoid

How to spot a Fenwick-tree problem

A mutable array with range sums

Count inversions with a Fenwick tree

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core1 problem

Application1 problem