Skip to content
Back to Data StructuresAll lessons

Data Structures

Fenwick Tree (Binary Indexed Tree)

update and prefixSum: O(log n) each. Every step jumps by a power of two, instead of visiting every element. This is much faster than recomputing a sum from scratch, at O(n), after every change.

The idea, in plain English

A Fenwick tree is like a row of donation jars, but a clever kind. One single running-total jar is slow to update. A full day-by-day list is slow to add up. Instead, each jar here covers a different-sized range of days. So getting 'the total so far' means peeking into just a handful of jars, not adding up every single day.

How it works

  1. 1Store values in a 1-indexed array. Position 0 is unused. Real data starts at position 1.
  2. 2update(i, delta): add delta to position i. Then hop to i plus i's lowest set bit, and repeat until you walk off the end. This updates every jar that covers position i.
  3. 3prefixSum(i): add up the jar at position i. Then hop to i minus i's lowest set bit, and repeat until you hit 0. This visits only O(log n) jars.
  4. 4rangeSum(l, r): just prefixSum(r) minus prefixSum(l − 1). This is the sum of everything up to r, minus everything before l.

When you'd use it

Use a Fenwick tree for running totals that change often, like live leaderboards, cumulative sales by day, or counting how many items are 'less than X' seen so far. Use it anywhere you need both fast updates and fast prefix sums.

Common beginner mistakes

  • Don't use index 0 for real data. Fenwick trees rely on 1-indexing. The math i & (-i) breaks down at index 0.
  • Don't reach for a Fenwick tree when values never change. If the data is fixed, a simple precomputed prefix-sum array is simpler and just as fast to query.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Sum of first 3: 15
Sum of 2..4: 19
Sum of first 3 after update: 25
Total sum: 39

See it in motion

Hop by powers of twoFenwick treeupdate and prefixSum: O(log n) each. Every step jumps by a power of two, instead of visiting every element. This is much faster than recomputing a sum from scratch, at O(n), after every change.
basetree152337495164010203040506

A 1-indexed base array (top) and its Binary Indexed Tree (bottom). Every jar covers a range of positions.

—
Index i
—
Sum
1/22
Step
0.0s
Time
Current jar / rangeSummed jarPosition of interestIdle jar

Not sure this is the right topic? See the learning paths → or where this leads →