Course contentsShow
← Computer Science
Lesson 649 of 2,87215. Tries and Specialized TreesFree lesson

Fenwick Tree (Binary Indexed Tree) Introduction

Understanding the Fenwick tree structure, its purpose for efficient prefix sum queries, and the basic intuition behind binary indexing.

Fenwick Tree (Binary Indexed Tree) Introduction

You'll learn what a Fenwick tree is and why it offers an elegant alternative to segment trees for prefix sum queries.

What Is a Fenwick Tree?

A Fenwick tree (also called a Binary Indexed Tree or BIT) is a specialized tree structure that efficiently handles dynamic arrays where you need to:

  • Calculate prefix sums (sum of elements from index 0 to i)
  • Update individual elements

While segment trees can handle these operations, Fenwick trees accomplish the same goals with simpler code and less memory—though they're specifically optimized for cumulative operations like sums.

The Core Intuition

Imagine you're tracking daily sales and frequently need to answer "What's the total from day 1 to day N?" After every sale, you update one day's value and must quickly recalculate any sum range.

A naive approach takes O(n) time per sum query. Fenwick trees reduce both queries and updates to O(log n) by cleverly storing partial sums at strategic positions. Instead of storing raw values or complete range sums like segment trees, each position in a Fenwick tree stores the sum of a specific number of preceding elements—determined by the binary representation of its index.

The "binary indexed" name comes from how the tree uses bit manipulation to navigate these relationships: each index is responsible for a range whose length is determined by the least significant bit in its binary form. This creates an implicit tree structure within a flat array.

Why Use Fenwick Trees?

  • Simpler implementation than segment trees (often just 10-15 lines)
  • Lower memory overhead (only one array needed)
  • Ideal for cumulative queries: prefix sums, frequency counts, range sums
  • Still achieves O(log n) for updates and queries

Key Takeaway: Fenwick trees use binary indexing to achieve O(log n) prefix sum queries and updates with elegant, compact code—making them perfect for dynamic cumulative array operations.