Home▸Algorithms & AI▸Fenwick Trees (Binary Indexed Trees): Fast Running Totals

🌳 Fenwick Trees (Binary Indexed Trees): Fast Running Totals

Explore how a Fenwick tree (binary indexed tree) keeps prefix sums of an array both easy to update and easy to query, using a simple lowest-set-bit trick.

Algorithms & AI3DModerate60 FPS

This simulator visualizes an 8-element Fenwick tree, showing how a single update ripples through only a few slots and how a prefix-sum query pulls together only a few partial sums to reach the answer.

🔬 What It Demonstrates

🎮 How to Use

Click an array position to update its value and watch which tree slots light up, or click a query position to see the log n chain of slots it visits to compute the running total.

💡 Did You Know?

Every index's lowest set bit is a power of two, so the number of slots touched during an update or query is bounded by the number of bits in the array size, which is why even a billion-element Fenwick tree needs at most about 30 steps.

⚙ Under the hood

Explore how a Fenwick tree (binary indexed tree) keeps prefix sums of an array both easy to update and easy to query, using a simple lowest-set-bit trick.

data-structuresalgorithmsfenwick-treebinary-indexed-treeprefix-sumscompetitive-programmingcomputer-sciencebit-manipulation

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install