Fenwick Tree Tutorial: Complete Guide 2026

Key Features of a Fenwick Tree

Let’s start with the key features of a Fenwick Tree to see what makes it efficient and useful:

1. Fast Updates and Queries

A Fenwick Tree lets you update values and calculate prefix sums in logarithmic time. It uses bitwise operations to figure out which elements need updating or summing. This is much faster than recalculating totals manually.

2. Memory Efficiency

It only needs the same amount of space as the original array. Partial cumulative sums are stored in a single one-dimensional structure, so there’s no extra memory needed for nodes or pointers.

3. Array-Based Implementation

Even though it works like a tree, it’s implemented using a simple array. Bitwise operations handle parent-child relationships, so there’s no need to build tree nodes or manage complicated pointers.

4. Handles Dynamic Data Well

Fenwick Trees can handle frequent updates and queries without hassle. You can change values or compute running sums without rebuilding the structure. This makes them great for real-time apps, analytics, or interactive programs.

5. Predictable Indexing

Most implementations use 1-based indexing. This aligns with the bitwise calculations for parent-child relationships and makes it easier to compute cumulative sums without errors.

Fenwick Tree vs Segment Tree

After looking at the key features of the tree, you might think it’s quite similar to a Segment Tree. However, the two are completely different in terms of performance and use cases. Here’s how the two compare:

Data Science Careers Aren’t Slowing Down: The global data science platform market size is projected to reach USD 470.92 billion by 2030, growing at a CAGR of 26.0% from 2024 to 2030. (Source: Grand View Research)

How Fenwick Tree Works

From the above comparison, it is clear that the trees are simpler and faster for basic sums. Let’s see exactly how it works:

1. Start with an Array

Suppose we have the array:

Original array: [3, 2, -1, 6]

We want a Fenwick Tree that quickly computes prefix sums and supports updates.

arr = [3, 2, -1, 6]
n = len(arr)
tree = [0]*(n+1) #index 0 unused
print(“Initial tree:”, tree)

2. Define Helper Functions

We need functions for the least significant bit (LSB), updating the tree, and querying prefix sums.

def lsb(i):
return i & -i
def update(tree, idx, delta):
while idx < len(tree):
tree[idx] += delta
idx += lsb(idx)
def query(tree, idx):
total = 0
while idx > 0:
total += tree[idx]
idx -= lsb(idx)
return total

3. Build the Tree (Step by Step)

A Fenwick Tree is typically stored 1-indexed, so for n = 4 the array should be size 5: Tree[0..4], with Tree[0] unused.

Let’s build it for values: a[1]=3, a[2]=2, a[3]=-1, a[4]=6.

Start: Tree = [0, 0, 0, 0, 0]

Step 1: add 3 at index 1

• Tree[1] += 3 → [0, 3, 0, 0, 0]
• next 1 + LSB(1)=2 → Tree[2] += 3 → [0, 3, 3, 0, 0]
• next 2 + LSB(2)=4 → Tree[4] += 3 → [0, 3, 3, 0, 3]

Step 2: add 2 at index 2

• Tree[2] += 2 → [0, 3, 5, 0, 3]
• next 2 + LSB(2)=4 → Tree[4] += 2 → [0, 3, 5, 0, 5]

Step 3: add -1 at index 3

• Tree[3] += -1 → [0, 3, 5, -1, 5]
• next 3 + LSB(3)=4 → Tree[4] += -1 → [0, 3, 5, -1, 4]

Step 4: add 6 at index 4

• Tree[4] += 6 → [0, 3, 5, -1, 10]

# Add 3 at index 1
update(tree, 1, 3)
print(“After adding 3 at index 1:”, tree)
# Add 2 at index 2
update(tree, 2, 2)
print(“After adding 2 at index 2:”, tree)
# Add -1 at index 3
update(tree, 3, -1)
print(“After adding -1 at index 3:”, tree)
# Add 6 at index 4
update(tree, 4, 6)
print(“After adding 6 at index 4:”, tree)

4. Compute a Prefix Sum

Find the sum of the first 3 elements (3 + 2 + -1 = 4)

• Start at index 3 → add Tree[3] = -1 → total = -1
• Move to 3 - LSB(3) = 2 → add Tree[2] = 5 → total = 4
• Move to 2 - LSB(2) = 0 → stop

prefix_sum_3 = query(tree, 3)
print(“Prefix sum up to index 3:”, prefix_sum_3)

Result: 4

5. Update a Value

Suppose we want to add 4 to the second element (changing 2 → 6).

• Start at index 2 → Tree[2] += 4 → [0, 3, 9, -1, 7]
• Next index = 2 + LSB(2) = 4 → Tree[4] += 4 → [0, 3, 9, -1, 11]

Now it reflects the updated array [3, 6, -1, 6].

update(tree, 2, 4) # add 4 to element at index 2
print(“Tree after adding 4 at index 2:”, tree)
# Query again after update
prefix_sum_3_updated = query(tree, 3)
print(“Prefix sum up to index 3 after update:”, prefix_sum_3_updated)

Result: 8

Building a Fenwick Tree (O(n) Method)

So far, you have seen how a Binary Index Tree works by updating each element one by one. You can also build the tree faster using the O(n) method, which constructs the entire tree in linear time. Here’s how it works:

1. Initialize the Tree Array

Make a tree array (BIT) with size n + 1 and leave index 0 empty.

Then copy the values from the original array into the tree array, starting at index 1.

Example:

Original array: [3, 2, -1, 6]

Tree array (initial): [0, 3, 2, -1, 6]

At this point, each index only stores its own value. The parent nodes haven’t started summing things up yet.

2. Propagate Values to Parent Nodes

For each index i from 1 to n:

1. Find the parent index: parent = i + LSB(i)
2. If parent <= n, add the value at i to the parent node

Why this works:

• Each node in the tree represents the sum of a range of elements.
• By adding a value to its parent, we ensure that all parent nodes correctly reflect the sum of the elements they cover.

Example:

Index 1: parent = 1+1 = 2 → BIT[2] + = BIT[1] → [0, 3, 5, -1, 6]

Index 2: parent = 2+2 = 4 → BIT[4] + = BIT[2] → [0, 3, 5, -1, 11]

Index 3: parent = 3+1 = 4 → BIT[4] + = BIT[3] → [0, 3, 5, -1, 10]

Index 4: parent = 4+4 = 8 → out of bounds → stop

Now all parent nodes contain the sum of elements in their respective ranges.

3. Final Tree Structure

After the updates, the BIT array is ready to use:

Final BIT: [0, 3, 5, -1, 10]

Each position in the array holds a partial sum. This setup makes it easy to get prefix sums or update values quickly, in about log(n) time.

4. Updating an Element in the Tree

Suppose we want to increase the 2nd element by 4 (from 2 to 6).
Propagate this change using the LSB rule:

BIT[2] + = 4 → [0, 3, 9, -1, 10]

Next parent: 2 + LSB(2) = 4 → BIT[4] + = 4 → [0, 3, 9, -1, 14]

The tree now reflects the updated logical array [3, 6, -1, 6].

Update Operation Explained

The update operation is what keeps the process fast when values change. Instead of recalculating everything, it only changes the parts of the tree that need it. Here’s how it works, step by step.

• Applying the Update at the Given Index

When a value at index i in the original array changes, the same change is first applied to the tree at index i. This index stores the sum of a range that directly includes the updated element, so it must be updated first.

• Using the Least Significant Bit

To decide which additional nodes are affected, the BIT Tree uses the least significant bit of the index. The expression i & -i extracts this bit and indicates the size of the range represented at that position.

• Moving Up the Tree

After updating the current index, the tree moves upward using the rule:

i = i + (i & -i)

Each new index reached represents a larger range that includes the updated element, so its stored sum must be adjusted accordingly.

• When the Update Stops

The update continues until the index exceeds the tree's size. At that point, all relevant nodes have been updated, and the tree is ready to answer prefix-sum queries correctly again.

Prefix Sum Query in O(log n)

Now that the tree is built and the update operation is clear, let’s see how prefix sum queries work:

• Reading the Stored Partial Sum

The query starts at index i in the tree. Instead of representing a single element, this position already stores the sum of a specific block of elements ending at i. That stored value is added directly to the result.

• Skipping Covered Ranges

Once a block is counted, there is no need to revisit the elements inside that range. To move past it, the Fenwick Tree reduces the index using the rule:

i = i - (i & -i)

This step jumps to the next index that represents a previous, non-overlapping block of elements.

• Accumulating the Result

At every new index, the agent adds another stored block sum to the total. It moves backward through the array in steps, making sure it doesn’t count anything twice or skip any elements.

• Query Completion

The process ends when the index becomes zero. By then, all required blocks have been collected, and their combined value gives the correct prefix sum up to the original index.

Fenwick Tree Implementation (C++)

C++ is a simple and efficient choice for implementing a Fenwick Tree. Let’s now see how the Fenwick Tree is written in C++: 

#include <iostream>
#include <vector>
using namespace std;
// Fenwick Tree (Binary Indexed Tree) implementation in C++
class FenwickTree {
private:
    int n;                // Size of the array
    vector<int> tree;     // The Fenwick Tree array (1-indexed)
public:
    // Constructor to initialize the Fenwick Tree with given size
    FenwickTree(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }
    // Update method: add 'delta' to element at index idx
    void update(int idx, int delta) {
        // Loop until index exceeds tree size
        while (idx <= n) {
            tree[idx] += delta;               // Add delta to current node
            idx += (idx & -idx);              // Move to next relevant node
        }
    }
    // Query method: returns prefix sum from 1 to idx
    int query(int idx) {
        int result = 0;
        while (idx > 0) {
            result += tree[idx];              // Add stored sum
            idx -= (idx & -idx);              // Move to parent node
        }
        return result;
    }
    // Method to build Fenwick Tree from an initial array
    void build(const vector<int> &arr) {
        for (int i = 1; i <= n; i++) {
            update(i, arr[i - 1]);             // Adjust for 1-based indexing
        }
    }
};
int main() {
    // Example usage
    vector<int> arr = {3, 2, -1, 6};
    int n = arr.size();
    // Create a Fenwick Tree of size n
    FenwickTree fenw(n);
    // Build the tree using the array
    fenw.build(arr);
    // Query prefix sum up to index 3
    cout << "Prefix sum up to index 3: " << fenw.query(3) << endl;
    // Update: add 4 at index 2
    fenw.update(2, 4);
    // Query again after update
    cout << "Prefix sum up to index 3 after update: " << fenw.query(3) << endl;
    return 0;
}

In this example, the first result prints the prefix sum up to index 3, which is 3 + 2 + (-1) = 4. After updating index 2 by adding 4, the array becomes [3, 6, -1, 6], so the prefix sum up to index 3 changes to 3 + 6 + (-1) = 8.

Python Code for Fenwick Tree

So that was the Fenwick Tree implementation in C++. Python also offers a clean and easy way to implement the same logic. Let’s now look at the Fenwick Tree code in Python.

class FenwickTree:
    def __init__(self, size):
        # Fenwick Tree uses a list of length (size + 1)
        # to support 1-based indexing
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, idx, delta):
        # Update the Fenwick Tree at position idx by adding delta
        while idx <= self.size:
            self.tree[idx] += delta
            idx += idx & -idx   # Move to next index that includes this in its range
    def query(self, idx):
        # Compute the prefix sum from 1 to idx
        result = 0
        while idx > 0:
            result += self.tree[idx]
            idx -= idx & -idx   # Move to parent index
        return result
    def build(self, arr):
        # Build the tree by updating each element once
        for i, val in enumerate(arr, start=1):
            self.update(i, val)
# Example usage
arr = [3, 2, -1, 6]
fenw = FenwickTree(len(arr))
fenw.build(arr)
# Query prefix sum up to index 3
print("Prefix sum up to index 3:", fenw.query(3))
# Update index 2 by adding 4
fenw.update(2, 4)
# Query again after update
print("Prefix sum up to index 3 after update:", fenw.query(3))

In this Python example, the first output shows the sum of the first few numbers up to index 3, which is 3 + 2 + (−1) = 4. Then we add 4 to the number at index 2, making the array [3, 6, −1, 6]. Now, the sum up to index 3 is 3 + 6 + (−1) = 8.

Real-World Applications and Examples

Here are some ways Fenwick Trees are used to update numbers or compute running totals quickly.

1. Efficient Range Sum and Prefix Sum Queries

Binary Index Trees are widely used to answer prefix-sum or range-sum queries when the data changes frequently. Instead of scanning the array every time, the tree can compute sums up to any index in logarithmic time, even after repeated updates.

This makes them ideal for scenarios such as cumulative statistics, dynamic scoreboards, or real-time analytics where performance matters.

2. Inversion Counting in Arrays

Inversion count problems, which count the number of pairs of array elements that are out of order, can be solved efficiently using Fenwick Trees. By processing the array from right to left and tracking the frequencies of elements seen so far, the tree helps compute the number of smaller numbers that precede each element in O(n log n) time.

3. Frequency Counting and Dynamic Histograms

Fenwick Trees are an excellent tool for monitoring event frequency as new data becomes available. Let's say you want to know how often each event appears in a stream. Updating counts and obtaining running totals without repeatedly going through all the data is made simple with a Fenwick Tree.

4. Finance and Time Series Analysis

BIT Trees are used in financial applications to calculate running metrics, such as aggregated financial indicators over time, moving totals of trades, and cumulative returns. The tree structure facilitates efficient updates and queries for real-time analysis when new data (such as stock prices or volumes) is continuously arriving.

5. Game Development and Leaderboards

Fenwick Trees are great for tracking scores in games where the leaderboard keeps changing. They let you quickly add points or update player positions without slowing anything down.

Common Problems and Practice

While Fenwick Trees are efficient, a few common problems often appear when implementing or using them:

• Indexing Confusion (0-based vs 1-based)

Fenwick Trees rely on 1-based indexing for their bitwise logic to work correctly. A common mistake is mixing 0-based arrays with 1-based tree indices, leading to incorrect updates or incomplete queries. Being consistent with indexing from the start is critical.

• Incorrect Use of the Least Significant Bit

The expression i & -i decides how the tree moves when you’re updating or querying it. If you use it incorrectly, the tree can get messed up. A common mistake for beginners is forgetting that updates go up the tree while queries go down the tree.

• Wrong Update Value

Fenwick Trees don’t actually store the real values. They keep track of the differences instead. If you try to change a value directly instead of updating the difference, your sums won’t come out right. This is a mistake I see a lot, and it usually breaks the prefix sums.

• Boundary and Size Errors

Problems often occur when updates or queries exceed the tree's size. Forgetting to stop when the index exceeds n can cause runtime errors or invalid memory access, especially in languages like C++.

• Choosing Fenwick Tree When Range Updates Are Needed

Fenwick trees are best suited for point updates and prefix or range-sum queries. Using them directly for complex range updates without proper techniques can lead to incorrect logic. Recognizing when a Fenwick Tree is a good fit for the problem is part of good practice.

Learn in-demand 30+ data science skills and tools, including database management, descriptive statistics, data visualization, inferential statistics, and LLM, with the Data Science Course.

Key Takeaways

• Fenwick Trees make it easy to quickly find sums of elements up to a point and update individual values
• Compared to Segment Trees, Fenwick Trees are simpler to implement and more memory-efficient, making them ideal for problems focused on cumulative sums
• Correct usage depends heavily on 1-based indexing and proper bitwise operations, such as i & -i, which control how updates and queries traverse the tree
• Fenwick Trees are widely applicable in competitive programming and real-world systems where data changes frequently and fast aggregate queries are required

FAQs

1. What is the time complexity of Fenwick Tree?

Both update and query operations run in O(log n) big O time complexity.

2. What is a Binary Indexed Tree (BIT)?

A Binary Indexed Tree, also called a Fenwick Tree, uses binary indexing to maintain prefix sums.

3. How to build a Fenwick Tree from an array?

It is built by starting with an empty tree and calling the update operation for each array element using 1-based indexing.

4. Fenwick Tree update vs query operations.

An update changes the value at a specific position, and a query sums all the values from the start up to a certain position.

5. Can Fenwick Tree handle range updates?

Yes, with modifications such as using two Fenwick Trees, it can support range updates alongside range queries.

6. Fenwick Tree implementation in Python.

It is implemented using a list with 1-based indexing and uses bitwise operations for update and query traversal.

7. Applications of the Fenwick Tree in coding.

It is commonly used in inversion counting, frequency tables, dynamic prefix sums, and competitive programming problems.

8. How do you find the kth-smallest element using the Fenwick Tree?

You can find the kth-smallest element pretty quickly by keeping track of how often each number appears and then searching the totals. This way, you don’t have to go through everything one by one.

9. What is the space complexity of Fenwick Tree?

The space complexity is O(n), where n is the size of the array.

10. Fenwick Tree for 2D range queries.

A 2D Fenwick Tree extends the concept to two dimensions and supports updates and queries in O(log² n) time.

11. Common mistakes in Fenwick Tree coding.

Common mistakes include using 0-based indexing, performing incorrect bitwise operations, and making off-by-one errors.

12. Fenwick Tree vs Prefix Sum array.

Prefix sum arrays support fast queries but slow updates, whereas Fenwick Trees support both efficiently.