Data Structures
Fenwick Tree (BIT)
Difficulty: Advanced
A complete Fenwick Tree implementation fits in fifteen lines of code, half the memory of a segment tree, and a smaller constant factor on every operation. The price of admission is that you only get prefix-style aggregates, but for the...
Fenwick Tree (BIT)
A complete Fenwick Tree implementation fits in fifteen lines of code, half the memory of a segment tree, and a smaller constant factor on every operation. The price of admission is that you only get prefix-style aggregates, but for the enormous class of problems that need exactly that, a Fenwick Tree (also called a Binary Indexed Tree, or BIT) is the right answer.
This lesson covers the dynamic prefix-sum problem (static prefix sums are O(1) query and O(n) update; you want both in O(log n)), the i & -i lowbit trick that isolates the lowest set bit and implicitly defines which range each index covers, point update and prefix query in O(log n), and the prefix(R) - prefix(L-1) identity that turns those into general range queries. You will also meet the difference-array technique that swaps the roles, supporting O(log n) range updates with O(log n) point queries.
In Arrays & Strings, you saw how a flat array can encode rich structure when the indexing scheme is clever; the Fenwick tree pushes that idea further by letting binary representation itself carry the partition information. Segment Tree solved a more general version of this problem with explicit nodes; the BIT trades flexibility for simplicity and memory and wins on both metrics whenever prefix queries suffice.
Next, Sparse Table addresses a different point in the trade space: arbitrary range minimum (and similar idempotent) queries, with O(1) queries when no updates are involved.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain why static prefix sums are insufficient when updates are needed, and how a Fenwick Tree solves this.
Describe how the lowbit operation (i & -i) determines the range each index is responsible for.
Implement point update and prefix query operations in O(log n) time.
Derive range queries from two prefix queries: sum(L, R) = prefix(R) - prefix(L-1).
Analyze time and space complexity of all Fenwick Tree operations.
Compare Fenwick Trees with segment trees and identify when each is the better choice.
Why This Matters
01
Fenwick Trees solve the dynamic prefix sum problem in O(log n) per operation, bridging the gap between static prefix sums (O(1) query, O(n) update) and full segment trees (more complex, more memory). For problems that only need prefix-based queries, a BIT is the simplest correct solution.
02
The lowbit trick (i & -i) used by Fenwick Trees is one of the most elegant applications of bit manipulation in data structure design. Understanding it deepens your grasp of how binary representation can encode structural information.
03
Fenwick Trees appear frequently in competitive programming contests (Codeforces, ICPC, LeetCode hard problems) for counting inversions, range frequency queries, and coordinate-compressed problems. They are also used in production systems for real-time analytics and cumulative statistics.
04
Because Fenwick Trees use half the memory of a segment tree and have a smaller constant factor, they are preferred in memory-constrained environments and when performance matters at scale.
Key Terms
7 terms you'll encounter in this lesson
Fenwick Tree
An array-based data structure (also called Binary Indexed Tree or BIT) that supports prefix sum queries and point updates in O(log n) time using O(n) space. Each index stores a partial sum covering a range whose length is determined by the lowest set bit of the index.
Binary Indexed Tree (BIT)
Another name for the Fenwick Tree, emphasizing that the binary representation of each index determines which range of the original array it aggregates.
Lowbit (Lowest Set Bit)
The operation i & (-i) which isolates the lowest set bit of an integer i. For example, lowbit(6) = lowbit(110_2) = 2 (10_2). In a Fenwick Tree, this value determines the range length each index is responsible for.
Prefix Query
A query that returns the sum (or other associative aggregate) of all elements from index 1 to index i. In a Fenwick Tree, this is computed by traversing indices that strip the lowest set bit at each step.
Point Update
An operation that adds a value delta to element at index i and propagates the change to all Fenwick Tree entries that include index i in their range, by repeatedly adding the lowest set bit to the index.
1-Based Indexing
Fenwick Trees use 1-based indexing because the lowbit trick does not work at index 0 (0 & -0 = 0, causing an infinite loop). The original array is mapped so that arr[0] corresponds to BIT index 1.
Range Query via Prefix Difference
The sum over range [L, R] is computed as prefix(R) - prefix(L-1). This reduces any range query to two prefix queries, which is the fundamental technique enabling Fenwick Trees to answer range queries.
Heads Up
Common misconceptions to watch out for
"A Fenwick Tree is a binary tree stored with pointers"
A Fenwick Tree is a flat array, not a pointer-based tree. The 'tree' in the name refers to the implicit parent-child relationships encoded by the binary representation of indices. There are no node objects or pointers -- just an array of partial sums.
"Fenwick Trees can replace segment trees in all cases"
Fenwick Trees efficiently support prefix-based operations (prefix sum, prefix min with special handling). Segment trees handle arbitrary range operations (range min/max queries with updates, range assignment) that Fenwick Trees cannot. When you need non-prefix-decomposable operations, a segment tree is required.
"Index 0 works fine in a Fenwick Tree"
Index 0 breaks the lowbit trick because 0 & -0 = 0, causing an infinite loop. Fenwick Trees use 1-based indexing. When your input is 0-indexed, add 1 to all indices when interfacing with the BIT.
"The Fenwick Tree stores the original array values"
Each position in the Fenwick Tree array stores a partial sum covering a specific range, not the original value. For example, BIT[6] stores the sum of original elements at indices 5 and 6 (a range of length lowbit(6) = 2). Only positions where the index is a power of 2 happen to cover just one element, but they still store that element's value as a partial sum.