理解树状数组（二进制索引树）

1. Introduction

A Fenwick tree, also called a binary indexed tree (BIT), is a data structure that can efficiently update elements and calculate range sums on a list of numbers. This tutorial will show how to construct a Fenwick tree to solve a mutable range sum query problem.

2. Problem Description

Let’s start with a mutable range sum query problem. Given an array of numbers with starting index of , we have two operations: and . For an operation, , we change the value of the element at the index to be . For a operation, , we calculate the sum of numbers between positions and inclusive. Our goal is to implement these two operations efficiently.

3. Brute Force Solution

For the operation, we can directly update the array element at the specified location. For the operation, we can iterate the array from index to and sum each element:

// In both functions:
//    A = a number array with size n
 
function Update(i, value):
    // INPUT
    //    i = index in array A where update occurs
    //    value = the new value to update at index i
    // OUTPUT
    //    Updates array A
     
    A[i] <- value

function Sum(left, right):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A 
     
    result <- 0
    for i <- left to right:
        result <- result + A[i]
    return result

In this solution, the operation takes time and operation takes time. The space requirement is .

4. Prefix Sum Solution

In order to have a faster operation, we can use the prefix sum approach. For the input array of numbers , the prefix sum at index is the sum of the prefix numbers ending at :

Based on the prefix sum definition, we can calculate a range sum with two prefix sums:

Given an array of numbers , let’s first construct a prefix sum array from :

algorithm PrefixSum(A, n):
    // INPUT
    //    A = a number array with size n
    // OUTPUT
    //    the prefix sum array of A

    prefix[0] <- 0

    for k <- 1 to n:
        prefix[k] <- prefix[k - 1] + A[k]

    return prefix

For the operation, we can directly answer the query with two prefix sum values. However, we need to update the prefix sum array for the operation:

// In both functions:
//    A = a number array with size n

function update(i, value):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A using prefix sum

    delta <- value - A[i]
    for k <- i to n:
        prefix[k] <- prefix[k] + delta
    A[i] <- value

function sum(left, right):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A using prefix array
    return prefix[right] - prefix[left - 1]

In this solution, the operation takes time and operation takes time. The space requirement is as we need an array to store prefix sums.

5. Fenwick Tree Solution

For the brute force and prefix sum solutions, either or operation takes time. If there are multiple and operations, these two solutions will take a lot of time. For example, if we have numbers of and operations, the overall time complexity will be for both solutions.

We can use a Fenwick tree to solve this problem more efficiently, as it only takes time for both and operations. Therefore, if we have numbers of and operations, the overall time complexity will be .

5.1. Range of Responsibility

When we make an operation, we have an input index parameter, , to indicate the update element location. Similarly, when we make a operation, we have an input index parameter, , to indicate the sum of the prefix numbers ending at . In the Fenwick tree solution, we do both operations based on the binary form of the input index . That’s the reason why we also call it a binary index tree.

In a Fenwick tree, each index has a range of responsibilities. We calculate the range of responsibility value based on the position of the rightmost set bit (RSB) in the binary representation of the index. For example, the binary representation of is . The range of responsibility of is then as its RSB gives value . Another example of a range of responsibilities is for the number . The range of responsibility of is as its RSB gives value .

5.2. Range of Responsibility Calculation

In computer science, we use the two’s complement method to produce a negative number from a positive number. Firstly, we reverse the ones and zeros of the binary representation of the positive number. Then we add one. Therefore, we can calculate the range of responsibility value of an index with the bit operation: .

For example, the binary value of in an 8-bit form is . After we reverse each bit, we have . When we add , every bit starting at the right will overflow into the next higher bit until we reach a bit, which is the RSB of the original positive number. Therefore, we can have .

When we do bitwise AND operation on the two numbers, we can get the range of responsibility value: .

Let’s define the range of responsibility calculation, , for an index :

algorithm RSB(i):
    // INPUT
    //    i = an index number
    // OUTPUT
    //    Range of responsibility of i

    return i & (-i)

5.3. Fenwick Tree Structure

The basic idea of the Fenwick tree solution is to precompute the responsibility range sum for each index. Then, we can calculate the prefix sum of an index based on the precomputed Fenwick values. Also, when we update the element at an index , we can only update those precomputed Fenwick values that cover the index .

Let denote the responsibility range sum for each index . For the array , we can have have an array where

The following table shows the Fenwick values for numbers from 1 to 16:

Number

Binary Representation

RSB

Fenwick

Based on the Fenwick value definition, we can see that one Fenwick value can cover several Fenwick values. For example, covers , and . We can use a tree structure to represent the coverage relationships:

In this Fenwick tree structure, leaf nodes are the index numbers. Each internal node represents a Fenwick value that can be constructed from its children Fenwick values and its own index array number. For example:

   

5.4. Fenwick Tree Construction

To construct a Fenwick tree, we can use a dynamic programming approach by propagating the smaller Fenwick values to the big Fenwick values:

algorithm ConstructFenwick(A, n):
    // INPUT
    //    A = a number array with size n
    // OUTPUT
    //    fenwick = the Fenwick array of A

    fenwick <- A

    for i <- 1 to n:
        parent <- i + RSB(i)
        if parent <= n:
            fenwick[parent] <- fenwick[parent] + fenwick[i]

    return fenwick

In this algorithm, we first initialize the Fenwick array with the input array . Then, we use a loop to propagate the smaller Fenwick values to their parent Fenwick values. The time complexity is .

We only need to construct the Fenwick array once at the beginning. In the future, we only need to update at most Fenwick values in an operation.

5.5. Prefix Sum Calculation

When we compute the prefix sum of index , we can start from index and go downwards until we reach :

algorithm PrefixSum(i):
    // INPUT
    //    i = an index
    //    fenwick = the Fenwick tree of array A
    // OUTPUT
    //    The prefix sum of A ending at index i

    result <- 0
    
    while i > 0:
        result <- result + fenwick[i]
        i <- i - RSB(i)
    
    return result

In this algorithm, we start from the input index and add its Fenwick value to the . Then, we remove the of and add the new Fenwick value into the . We keep doing this process until we reach index .

Suppose we want to find the prefix sum for index . Firstly, we add into our . Then, we subtract the value of , which is , and reach a new index . Therefore, we add into our . Again, we subtract from and get a new index . Similarly, we add into our . Finally, we subtract from the current index and stop the loop as we reach the index .

In the end, we can have .

The time complexity of this algorithm is as we remove one set bit of the original index in each iteration until we reach .

5.6. Fenwick Tree Update

The operation is the opposite of operation. We start from the input index and go upwards along the tree path to propagate the operation.

Suppose we want to add a value at the location . We can first add to . Then, we get its parent based on the and reach the index . Therefore we also add to . Similarly, we continue to update the parent Fenwick values like and until we reach the array size boundary :

algorithm UpdateFenwickTree(i, delta):
    // INPUT
    //    i = an index to update
    //    fenwick = the Fenwick tree of array A
    //    delta = the value to add
    // OUTPUT
    //    Fenwick tree is updated with the delta value at index i

    while i <= n:
        fenwick[i] <- fenwick[i] + delta
        i <- i + RSB(i)

Similar to the , the time complexity of is .

5.7. Fenwick Tree Solution

We can combine the above functions to solve the mutable range sum query problem:

// In both functions:
//    A = a number array with size n

function update(i, value):
    // INPUT
    //    i = index in array A where update occurs
    //    value = the new value to update at index i
    // OUTPUT
    //    Updates the Fenwick tree and array A
    delta <- value - A[i]
    add(i, delta)
    A[i] <- value

function sum(left, right):
    // INPUT
    //    left = the left index of the range to sum
    //    right = the right index of the range to sum
    // OUTPUT
    //    The sum of elements between left and right in the array A using Fenwick Tree
    return prefixSum(right) - prefixSum(left - 1)

In the function, we first calculate the of the updated value, Then, we call the function to update the Fenwick tree. The time complexity is as we only call the function once.

In the function, we call function twice to get the sum between and . The overall time complexity is still .

The space complexity of the Fenwick solution is as we need to store the Fenwick values for all the indexes.

6. Conclusion

In this article, we showed how to use a Fenwick tree to solve the mutable range sum problem. With the Fenwick tree, we can achieve time for both and operations.