Skip to content
CCC Python Course

Fenwick tree (Binary Indexed Tree)

Stage
6
Module
M6.10
Lessons
1

In this module

  • Understand how a Fenwick tree stores partial sums with O(log n) operations.
  • Implement update and range-sum queries using bit manipulation.
  • Apply Fenwick trees to dynamic range-sum problems where prefix sums fail.

Before this module

M4.3Prefix sums (1D, 2D, prefix/suffix max)M2.9Complexity analysis and deriving the target from N

Lessons

  1. 1Fenwick tree (Binary Indexed Tree)

Practice

Try these on the judge. Each link opens the problem on DMOJ.

  1. 2019 J5
    Rule of Three (opens on DMOJ in a new tab) DMOJ

    Calculate how the number of each item changes across growing inventory.

  2. 2020 S1
    Surmising a Sprinter's Speed (opens on DMOJ in a new tab) DMOJ

    Work with a sprinter's recorded checkpoint times to find a consistent picture of the race.