Understanding Fenwick Tree in Computer Science

Introduction and Core Concepts

The fenwick tree, also known as the Binary Indexed Tree (BIT), is one of the most elegant and efficient data structures for maintaining dynamic prefix sums and solving range query problems. Introduced by Peter M. Fenwick in 1994 for efficient arithmetic coding, the fenwick tree has since become a staple in competitive programming, database systems, and high-performance computing. It provides a perfect balance between simplicity, memory efficiency, and logarithmic time performance for both updates and queries.

At its core, a fenwick tree is designed to solve the dynamic prefix sum problem. Given an array arr[1..n], we want to support two fundamental operations efficiently: updating the value at a single index and computing the sum of elements in a prefix arr[1] + arr[2] + ... + arr[i] or a range arr[l] + ... + arr[r]. A naive array requires O(n) time for range sum queries, while a simple prefix sum array requires O(n) time for updates. The fenwick tree achieves O(log n) time for both operations using only O(n) additional memory and an incredibly compact implementation.

Why does the fenwick tree matter? In real systems, data is rarely static. Stock prices fluctuate, user activity counters increment continuously, frequencies in data streams change, and cumulative distributions need to be maintained under updates. Any application that needs to answer questions like "how many events occurred in the last hour?" or "what is the total score of players ranked 10 to 50?" while handling thousands of updates per second can benefit from this structure. Its cache-friendly array representation, minimal memory overhead, and ease of implementation make it often preferable to more complex structures like segment trees when only cumulative sum operations are required.

Key Properties of the Fenwick Tree

A fenwick tree is not a tree in the traditional pointer-based sense. It is an implicit data structure stored in a single array BIT[1..n] where each position stores the sum of a specific range of the original array. The range covered by each index is determined by the lowest set bit of that index, a property derived from the binary representation of numbers. This clever encoding allows the structure to navigate and combine ranges using only bitwise operations.

Unlike a segment tree which explicitly stores intervals in a binary tree with up to 4n nodes, the fenwick tree stores exactly n values and uses the binary indexing trick to implicitly define the tree hierarchy. This makes it extremely memory efficient and fast in practice due to excellent locality of reference. All operations are iterative and involve simple loops that traverse O(log n) indices by adding or subtracting the lowest set bit.

The fenwick tree is most powerful when the operation being performed is invertible, such as sum, product, or xor. While it can be adapted for operations like minimum or maximum with limitations, its canonical and most efficient use case is for sum queries where both point updates and prefix queries are needed dynamically. Understanding this core trade-off is essential for choosing it over alternatives.

How It Works

The magic of the fenwick tree lies in the concept of responsible intervals and the lowbit function. Define lowbit(x) = x & -x, which isolates the lowest set bit of x in binary. For example, lowbit(12) = lowbit(1100) = 4 (0100), and lowbit(6) = lowbit(0110) = 2 (0010). In a fenwick tree, the element at index i in the BIT array stores the sum of lowbit(i) consecutive elements from the original array, ending at i. Specifically, BIT[i] = sum of arr[i - lowbit(i) + 1 .. i].

This definition creates a hierarchical covering of the array. For instance, with n=8: BIT[1] stores arr[1], BIT[2] stores arr[1..2], BIT[3] stores arr[3], BIT[4] stores arr[1..4], BIT[5] stores arr[5], BIT[6] stores arr[5..6], BIT[7] stores arr[7], and BIT[8] stores arr[1..8]. Notice how powers of two cover larger blocks, while odd indices cover only a single element. This structure ensures that any prefix sum prefix(i) can be decomposed into O(log n) disjoint blocks stored in the BIT.

To compute a prefix sum up to index i, we start at i and repeatedly remove its lowbit: i = i - lowbit(i), accumulating BIT[i] at each step. To perform a point update that adds delta to arr[i], we must update all BIT entries that cover i. These are found by repeatedly adding lowbit: i = i + lowbit(i) until we exceed n. Both traversals visit at most log2(n) indices because each step flips the lowest set bit to zero or propagates a carry, effectively moving up the implicit tree.

The Binary Representation Insight

Another way to understand the fenwick tree is through binary decomposition. Any integer i can be represented as a sum of powers of two. For example, 13 = 8 + 4 + 1. The prefix sum up to 13 can therefore be expressed as BIT[13] + BIT[12] + BIT[8], where 13 covers 1 element (13..13), 12 covers 4 elements (9..12), and 8 covers 8 elements (1..8). The query algorithm automatically performs this decomposition by stripping lowbits.

This binary lifting property is what gives the fenwick tree its logarithmic guarantee. The number of set bits in any number up to n is at most log2(n), and the traversal for both query and update visits one index per bit manipulation step. The structure is also intimately related to the binary representation of indices in a way that makes it amenable to other operations like finding the smallest index with a given cumulative frequency, often called order statistic or kth element search, in O(log n) time.

Compared to a naive prefix sum array that must shift all subsequent elements on an update, the fenwick tree distributes responsibility so that each original element contributes to exactly O(log n) BIT entries. Specifically, arr[i] contributes to BIT[i], BIT[i + lowbit(i)], BIT[i + lowbit(i) + lowbit(i + lowbit(i))], and so on. This limited propagation is the key to its efficient update performance.

Implementation

Implementing a fenwick tree is remarkably concise. The entire structure can be written in under 30 lines of Python while remaining fully functional and efficient. The 1-based indexing is crucial; most implementations allocate an array of size n+1 and ignore index 0 to simplify the lowbit arithmetic. If your input array is 0-based, you simply shift indices by +1 when calling update and query operations.

Below is the canonical implementation supporting point updates and prefix sum queries. Range sum queries are then answered as prefix(r) - prefix(l-1). The code uses the idiom idx & -idx to compute lowbit efficiently, which works due to two's complement representation of negative integers.

class FenwickTree:
    def __init__(self, n):
        # n: size of original array (1-indexed)
        self.n = n
        self.bit = [0] * (n + 1)  # bit[0] unused

    def update(self, idx, delta):
        """Add delta to element at idx (1-indexed). O(log n)"""
        while idx <= self.n:
            self.bit[idx] += delta
            idx += idx & -idx  # move to next responsible node

    def query(self, idx):
        """Return prefix sum arr[1] + ... + arr[idx]. O(log n)"""
        s = 0
        while idx > 0:
            s += self.bit[idx]
            idx -= idx & -idx  # remove lowbit
        return s

    def range_sum(self, l, r):
        """Return sum of arr[l..r] inclusive. O(log n)"""
        if l > r:
            return 0
        return self.query(r) - self.query(l - 1)

Building the tree from an initial array can be done naively by calling update for each element, which costs O(n log n). However, a linear O(n) construction exists by directly propagating values in order. This optimized build leverages the fact that BIT[i] is responsible for a range ending at i, so we can accumulate its value into its parent j = i + lowbit(i) in a single pass.

class FenwickTreeOptimized:
    def __init__(self, arr):
        # arr is 0-indexed input list
        self.n = len(arr)
        self.bit = [0] * (self.n + 1)
        self.build(arr)

    def build(self, arr):
        """Build BIT in O(n) time"""
        # Step 1: copy values to BIT (1-indexed)
        for i, val in enumerate(arr, 1):
            self.bit[i] += val
            # Propagate to parent
            j = i + (i & -i)
            if j <= self.n:
                self.bit[j] += self.bit[i]

    def update(self, idx, delta):
        while idx <= self.n:
            self.bit[idx] += delta
            idx += idx & -idx

    def query(self, idx):
        s = 0
        while idx > 0:
            s += self.bit[idx]
            idx -= idx & -idx
        return s

    # Alternative O(n log n) build for comparison
    def build_naive(self, arr):
        for i, val in enumerate(arr, 1):
            self.update(i, val)

For many problems, we need more advanced operations such as range updates and point queries, or range updates and range queries. The standard fenwick tree can be extended to support these with one or two BITs using clever mathematical transformations. A common technique uses the identity that adding v to range [l, r] can be simulated by point updates on a difference array.

class FenwickRangeUpdate:
    """Supports range add and point query using one BIT"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 2)

    def _add(self, idx, delta):
        while idx <= self.n:
            self.bit[idx] += delta
            idx += idx & -idx

    def range_add(self, l, r, val):
        """Add val to every element in [l, r]. O(log n)"""
        self._add(l, val)
        self._add(r + 1, -val)

    def point_query(self, idx):
        """Get value at idx after range adds. O(log n)"""
        s = 0
        while idx > 0:
            s += self.bit[idx]
            idx -= idx & -idx
        return s

class FenwickRangeUpdateRangeQuery:
    """Supports range add and range sum query using two BITs"""
    def __init__(self, n):
        self.n = n
        self.bit1 = [0] * (n + 2)
        self.bit2 = [0] * (n + 2)

    def _add(self, bit, idx, val):
        while idx <= self.n:
            bit[idx] += val
            idx += idx & -idx

    def _sum(self, bit, idx):
        s = 0
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx
        return s

    def range_add(self, l, r, val):
        # Update both BITs to maintain prefix sum formula
        self._add(self.bit1, l, val)
        self._add(self.bit1, r + 1, -val)
        self._add(self.bit2, l, val * (l - 1))
        self._add(self.bit2, r + 1, -val * r)

    def prefix_sum(self, idx):
        return self._sum(self.bit1, idx) * idx - self._sum(self.bit2, idx)

    def range_sum(self, l, r):
        return self.prefix_sum(r) - self.prefix_sum(l - 1)

Another powerful capability is the order statistic search, finding the smallest index idx such that prefix(idx) >= k. This is invaluable for problems like finding the kth one in a binary array, dynamic median maintenance, or implementing an order statistic tree. It runs in O(log n) using binary lifting on the BIT structure, similar to searching in a binary indexed tree.

class FenwickWithFindKth(FenwickTree):
    def find_kth(self, k):
        """Find smallest idx such that prefix sum >= k.
           Assumes all values are non-negative and k >= 1.
           Returns n+1 if not found. O(log n)"""
        if k <= 0:
            return 0
        idx = 0
        # Largest power of two <= n
        bit_mask = 1 << (self.n.bit_length() - 1)
        while bit_mask != 0:
            t = idx + bit_mask
            if t <= self.n and self.bit[t] < k:
                idx = t
                k -= self.bit[t]
            bit_mask >>= 1
        return idx + 1

# Example usage:
# ft = FenwickWithFindKth(8)
# for i, v in enumerate([1,0,1,1,0,1,0,1], 1):
#     ft.update(i, v)
# print(ft.find_kth(3))  # returns 4 (3rd one is at index 4)

Step-by-Step Example

Let us walk through a concrete example to solidify the mechanics. Consider the original array arr = [3, 2, -1, 6, 5, 4, -3, 3] with n=8 (1-indexed for the fenwick tree). We will build the BIT, perform a query, and then execute an update, observing how the internal array changes at each step.

First, we compute the BIT array using the definition BIT[i] = sum(arr[i - lowbit(i) + 1 .. i]). Calculating lowbit for each index: lowbit(1)=1, lowbit(2)=2, lowbit(3)=1, lowbit(4)=4, lowbit(5)=1, lowbit(6)=2, lowbit(7)=1, lowbit(8)=8. Therefore: BIT[1]=3, BIT[2]=3+2=5, BIT[3]=-1, BIT[4]=3+2-1+6=10, BIT[5]=5, BIT[6]=5+4=9, BIT[7]=-3, BIT[8]=3+2-1+6+5+4-3+3=19. The internal BIT array (ignoring index 0) is [3, 5, -1, 10, 5, 9, -3, 19].

Now, let us query the prefix sum up to index 6, which should be 3+2-1+6+5+4=19. The query algorithm starts at idx=6: add BIT[6]=9 to sum (sum=9), then idx = 6 - lowbit(6)=6-2=4. Add BIT[4]=10 (sum=19), then idx=4-4=0, loop terminates. The result 19 matches the expected sum. Notice we only visited indices 6 and 4, not all six elements. For a range sum query like sum(3..6), we compute query(6)-query(2)=19-5=14, which equals -1+6+5+4=14.

Performing an Update

Suppose we want to add +2 to arr[3], changing it from -1 to 1. The update must propagate to all BIT nodes that cover index 3. Starting at idx=3: BIT[3] +=2 becomes 1, then idx=3+lowbit(3)=3+1=4: BIT[4] +=2 becomes 12, then idx=4+4=8: BIT[8] +=2 becomes 21, then idx=8+8=16 which exceeds n, so we stop. The updated BIT array is [3, 5, 1, 12, 5, 9, -3, 21]. Only three entries were modified, demonstrating O(log n) update cost.

Let us verify correctness after the update. The new array is [3,2,1,6,5,4,-3,3]. Querying prefix(6) again: idx=6 adds BIT[6]=9 (sum=9), idx=4 adds BIT[4]=12 (sum=21). The expected sum is 3+2+1+6+5+4=21, which matches. Querying prefix(3): idx=3 adds BIT[3]=1 (sum=1), idx=2 adds BIT[2]=5 (sum=6). Expected 3+2+1=6, correct. This walkthrough shows how the fenwick tree maintains consistency with only logarithmic propagation.

This example also illustrates why 1-based indexing is essential. With 0-based indexing, lowbit(0) is 0, causing an infinite loop, and the binary trick breaks down. The transformation is trivial: if you have a 0-based array, always call update(i+1, delta) and query(i+1) to map correctly. Many bugs in fenwick tree implementations stem from off-by-one errors in this translation, so careful handling of indices is critical.

Complexity Analysis

The fenwick tree offers excellent and predictable performance characteristics. Both point update and prefix query operations run in O(log n) time in all cases, as the number of steps is determined solely by the binary representation of the index and the size n, not by the data values. This worst-case guarantee is stronger than many other data structures that may have average-case logarithmic behavior but degrade under certain inputs.

Space complexity is O(n) for the BIT array plus O(1) auxiliary space. This is optimal, as we must store n values anyway, and the fenwick tree adds only a constant factor overhead. There is no recursion stack, no pointers, and no extra bookkeeping structures, making it extremely memory efficient. In contrast, a segment tree typically requires 2n to 4n space depending on implementation, and a balanced binary search tree requires additional pointers and metadata per node.

Construction time depends on the method used. The naive method of performing n point updates takes O(n log n) time, which is acceptable for n up to a few hundred thousand. The optimized linear build runs in O(n) time by processing indices in increasing order and propagating each BIT[i] to its parent once. This optimization is significant for large n or when rebuilding the structure frequently. The query for a range sum requires two prefix queries, so it remains O(log n) with a small constant factor of 2.

It is worth noting that the constant factors for fenwick tree operations are very small. Each iteration performs only a few array accesses, an addition or subtraction, and a bitwise AND operation. This makes it highly competitive in practice, often 2 to 3 times faster than a segment tree for equivalent sum queries due to better cache performance and fewer operations per level. The iterative nature also avoids recursion overhead and stack limits.

For two-dimensional fenwick trees, which support point updates and rectangle sum queries, the complexities become O(log n * log m) for both operations with O(n*m) space. While the logarithmic factor squares, it remains efficient for moderate grid sizes and is widely used in image processing and matrix query problems. The extension to higher dimensions follows the same pattern, with complexity O(log^d n) for d dimensions.

Variations and Optimizations

The classic fenwick tree has spawned numerous variations to handle broader classes of problems. The most common extension is the range update point query (RUPQ) and range update range query (RURQ) variants described in the implementation section. These use one or two BITs to support adding a value to an entire interval and then querying either a single point or the sum of an interval, all in logarithmic time. The two-BIT technique for RURQ relies on the mathematical identity that the prefix sum after range adds can be expressed as a linear function of the BIT queries.

Another important variation is the 2D fenwick tree, which generalizes the structure to matrices. In a 2D BIT, each cell (x,y) stores the sum of a rectangle whose size is determined by lowbit(x) and lowbit(y). Updates propagate in both dimensions by adding lowbits, and queries combine O(log n * log m) rectangles. This is particularly useful for dynamic 2D range sum problems, such as maintaining counts in a grid with point updates and rectangle queries, and is simpler to implement than a 2D segment tree.

For operations that are not invertible, like range minimum query with point updates, the standard fenwick tree cannot efficiently support both operations in O(log n). However, a fenwick tree can support prefix minimum queries with point updates where updates only decrease values, or it can support range minimum queries with point updates in O(log n) for query but O(n) for update in the worst case. For fully dynamic range minimum or maximum, a segment tree is generally the better choice.

Advanced Optimizations

One optimization is coordinate compression, which is essential when indices are large but sparse. For example, if you need to handle values up to 10^9 but only have 10^5 distinct indices, you can compress the coordinates to the range 1..10^5 and use a fenwick tree of that size. This technique is ubiquitous in offline query processing and when using fenwick trees for counting inversions or handling large value ranges.

Another optimization involves using a fenwick tree for frequencies to implement an order statistic tree. By storing 1 at positions that are present and 0 otherwise, the prefix sum gives the rank of an element, and find_kth gives the element by rank. This allows for dynamic order statistics, including finding medians, percentiles, and handling deletions and insertions, all in O(log n) time with minimal code compared to a balanced BST.

For high-performance scenarios, cache optimization and bit manipulation tricks can further accelerate the fenwick tree. Since the access pattern is somewhat scattered, ensuring the BIT array fits in cache and using iterative loops with local variables helps. Some implementations also use a binary indexed tree with 0-based indexing using the transformation idx = idx | (idx + 1) for updates and idx = (idx & (idx + 1)) - 1 for queries, which avoids the 1-based shift but is less intuitive. The choice between 0-based and 1-based is largely stylistic, but 1-based remains more common due to its direct lowbit formulation.

Real-World Applications

Fenwick trees are not merely academic curiosities; they power critical components in production systems where efficient cumulative queries are needed. In web servers and analytics platforms, they are used to maintain real-time histograms and frequency tables. For example, a web server handling millions of requests per second might use a fenwick tree to track the distribution of response times or status codes by bucket, allowing it to answer queries like "how many requests had latency between 100ms and 200ms in the last minute?" with logarithmic updates as each request completes.

In databases and data warehouses, fenwick trees support efficient maintenance of cumulative aggregates for online analytical processing (OLAP). When a database needs to maintain materialized views with running totals or support range aggregation queries over streaming inserts, a fenwick tree can provide O(log n) maintenance versus O(n) recomputation. They are also used in columnar stores to support compressed bitmap indexes and to quickly compute prefix sums over encoded data for query optimization.

Networking and systems programming leverage fenwick trees for resource allocation and scheduling. In operating systems, they can manage free memory blocks or process priorities where prefix sums represent cumulative resource usage. In network routers, fenwick trees help with IP routing table lookups and packet scheduling algorithms that require weighted fair queuing based on prefix sums of weights. The ability to find the kth element quickly is particularly useful for implementing efficient priority queues with dynamic weights.

Applications in Algorithms and Data Science

In algorithmic problem solving, the fenwick tree is a go-to tool for counting inversions in an array, a classic problem that arises in measuring array sortedness and in collaborative filtering. By processing elements from left to right and querying how many larger elements have been seen, inversions can be counted in O(n log n) time. Similarly, it is used for offline range query processing, such as answering many queries of the form "how many numbers in [l,r] are less than k?" by sorting queries and using a BIT over positions.

In data science and machine learning, fenwick trees support efficient sampling from discrete distributions that change over time. The alias method and fenwick-based sampling allow for O(log n) updates to weights and O(log n) sampling proportional to weights, which is crucial for algorithms like weighted random sampling, particle filters, and reinforcement learning where action probabilities are updated continuously. They are also used in arithmetic coding, the original motivation for Fenwick's work, where cumulative frequencies must be maintained for entropy coding.

Financial systems use fenwick trees to maintain order books and cumulative trading volumes. A stock exchange might need to quickly compute the total volume of orders at price levels up to a certain price, or find the price level where cumulative volume exceeds a threshold, both of which map directly to prefix sum and find_kth operations. The low latency and predictable performance of the fenwick tree make it ideal for high-frequency trading environments where microseconds matter.

Comparison with Alternatives

Choosing the right data structure for range queries depends on the specific operations required, implementation complexity, and performance constraints. The fenwick tree excels at sum-like operations with point updates and prefix or range queries, but other structures may be more appropriate when different operations or more general intervals are needed. Understanding the trade-offs is essential for system design and interview problem solving.

The most direct alternative is the segment tree, which is more general and can handle any associative operation including sum, min, max, gcd, and even custom merges, for arbitrary range queries and range updates with lazy propagation. However, this generality comes at the cost of higher memory usage (up to 4n), more complex code, and larger constant factors. For pure sum queries, the fenwick tree is almost always faster and simpler. If you need range minimum queries with range updates, or non-invertible operations, the segment tree is the correct choice.

A simple prefix sum array offers O(1) range queries after O(n) preprocessing but requires O(n) time for any point update, making it suitable only for static arrays. A sparse table provides O(1) range queries for idempotent operations like min or max after O(n log n) preprocessing but cannot handle updates at all. Balanced binary search trees and binary indexed trees with order statistics can handle dynamic order statistics but are more complex to implement for sum queries. For many practical cases, the fenwick tree hits the sweet spot of supporting dynamic updates and queries with minimal overhead.

In practice, many experienced engineers default to the fenwick tree when the problem involves only sums and point updates because of its brevity and speed. In coding interviews, implementing a fenwick tree correctly and quickly can be a strong signal, while a segment tree implementation is more error-prone under time pressure. However, recognizing when the fenwick tree is insufficient, such as when you need to query the minimum on an arbitrary interval with updates, demonstrates deeper understanding of data structure trade-offs.

Another consideration is persistence and functional variants. Both fenwick trees and segment trees can be made persistent to support versioned queries, but the segment tree's explicit tree structure makes persistence more natural. For most dynamic prefix sum problems, though, the non-persistent fenwick tree is sufficient and optimal.

Common Mistakes and Best Practices

Even though the fenwick tree is simple, several pitfalls frequently trap newcomers. The most common mistake is mixing 0-based and 1-based indexing. The BIT array must be 1-indexed for the lowbit trick to work correctly. Forgetting to shift indices by +1 when interfacing with a 0-based input array leads to incorrect results or infinite loops when idx=0 is queried. Always be explicit about indexing in your interface and document whether your methods expect 0-based or 1-based indices.

Another frequent error is using the wrong loop condition. For updates, the loop is while idx <= n, not < n, because the BIT array has size n+1 and index n is valid. For queries, the loop is while idx > 0, not >= 0, because BIT[0] is unused and accessing it would be incorrect. Off-by-one errors here cause silent failures where the last element is never updated or queried. Testing with small arrays where you manually compute expected BIT values is the best way to catch these bugs.

A subtle mistake is not handling negative numbers or large sums correctly. The fenwick tree works with any integer values, but if you use it for counting frequencies and then perform find_kth, you must ensure values are non-negative and that k is valid. For sum queries with large n and large values, integer overflow can occur in languages with fixed-size integers; in Python this is not an issue due to arbitrary precision integers, but in C++ or Java you may need 64-bit types. Also, when supporting range updates with two BITs, the formulas for updating bit1 and bit2 are easy to get wrong, so derive them carefully or memorize the standard pattern.

Best Practices

To write robust fenwick tree code, follow these best practices. First, encapsulate the structure in a class with clear method names like update, query, and range_sum, and include docstrings that specify indexing and time complexity. This improves readability and reduces misuse. Second, provide both O(n log n) and O(n) build methods and choose the linear build when initializing from a known array for better performance.

Third, always test edge cases: n=1, queries with l=r, queries with l=1, updates at the first and last positions, and sequences of interleaved updates and queries. Compare your BIT results against a naive array for random operations in a test harness to verify correctness. Fourth, when you need range updates, write helper methods _add and _sum to avoid duplicating loop logic and to make the two-BIT implementation less error-prone.

• Use 1-based indexing internally and convert at the API boundary if needed. Never expose 0-based lowbit logic.
• Escape lowbit as a helper function def lowbit(x): return x & -x for clarity, or inline as x & -x for brevity, but be consistent.
• For find_kth, ensure the tree contains only non-negative values and handle the case where k exceeds total sum.
• Prefer iterative loops over recursion for both performance and to avoid recursion depth limits.
• Document whether your range_sum is inclusive or exclusive; inclusive [l,r] is standard for fenwick trees.
• When compressing coordinates, sort unique values and map them to 1..m before building the BIT.

Finally, recognize the limitations of the fenwick tree and do not force it where a segment tree is more appropriate. If you find yourself trying to support range minimum queries with range updates using a fenwick tree, step back and consider whether a segment tree with lazy propagation would be cleaner and more correct. Choosing the right tool for the job is a hallmark of strong engineering judgment.

Interview Questions

Fenwick trees appear frequently in technical interviews, especially for roles involving algorithms, data engineering, or high-performance systems. Interviewers use them to assess understanding of data structures, bitwise manipulation, and the ability to optimize from O(n) to O(log n). Below are common interview questions that test different aspects of fenwick tree knowledge, along with guidance on how to approach them.

Question 1: Range Sum Query - Mutable

Problem: Given an integer array nums, handle multiple queries of two types: update(i, val) to update nums[i] to val, and sumRange(l, r) to return the sum of nums[l..r]. This is LeetCode 307. How would you solve it efficiently?

Approach: This is the canonical fenwick tree problem. Explain the naive O(n) per query solution and why it is too slow for many queries. Then present the fenwick tree solution with O(log n) per operation. Discuss 1-based indexing, the update method that computes delta = val - nums[i] and propagates it, and the range sum as query(r+1)-query(l). Mention the O(n) build optimization and compare with segment tree alternative. Be prepared to code the FenwickTree class live and handle 0-based to 1-based conversion. Time complexity O(log n) per operation, space O(n).

Question 2: Count of Smaller Numbers After Self

Problem: Given an array nums, return an array counts where counts[i] is the number of smaller elements to the right of nums[i]. This is LeetCode 315.

Approach: This tests coordinate compression plus fenwick tree. The solution involves compressing values to ranks 1..m, processing the array from right to left, and using a BIT over frequencies. For each nums[i], query prefix sum up to rank-1 to count smaller elements already seen, then update rank with +1. Explain why processing right to left works and why compression is needed for large value ranges. Complexity O(n log n) time, O(n) space. Alternative solutions using merge sort or BST can be mentioned, but fenwick tree is often the cleanest.

Question 3: Counting Inversions

Problem: Count the number of inversions in an array, where an inversion is a pair (i,j) with i < j and arr[i] > arr[j].

Approach: Similar to the previous problem, this is a classic fenwick tree application. Compress the array values, iterate from left to right or right to left, and use BIT to count how many greater or smaller elements have been seen. For left-to-right: for each element, query total seen - query(rank) to count greater elements seen so far. Sum these counts. Discuss the O(n log n) solution versus the O(n^2) brute force and the O(n log n) merge sort alternative. This question tests understanding of how fenwick trees can count frequencies and answer order statistics dynamically.

Question 4: Find Kth One in a Binary Array with Updates

Problem: You have a binary array with operations: flip a bit at index i, and find the index of the kth 1 in the array.

Approach: This tests the find_kth operation. Maintain a fenwick tree over the binary array where each position stores 0 or 1. Flipping is a point update with delta = +1 or -1. Finding the kth one is exactly the find_kth method using binary lifting on the BIT in O(log n). Explain the binary lifting technique, why it works only for non-negative frequencies, and how to handle the case where k is larger than total ones. This is more advanced and demonstrates deep understanding of fenwick tree internals beyond basic sum queries.

Question 5: 2D Range Sum Query - Mutable

Problem: Given a 2D matrix, support updating a single cell and querying the sum of a submatrix defined by its corners.

Approach: This extends the fenwick tree to two dimensions. Describe the 2D BIT where update propagates in both x and y dimensions using nested loops with lowbit, and query combines O(log n log m) cells. Explain the inclusion-exclusion principle for rectangle queries: sum(x2,y2) - sum(x1-1,y2) - sum(x2,y1-1) + sum(x1-1,y1-1). Discuss time complexity O(log n log m) per operation and space O(n*m). Compare with 2D segment tree and prefix sum array, and mention when to choose each. This question is for senior or specialized roles