What is a Fenwick Tree?

A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that allows efficient querying and updating of cumulative sums of elements in an array.

It was invented by Peter Fenwick in 1994 and is commonly used in computational geometry, graph algorithms, and other applications where prefix sums and range queries are required.

The Fenwick Tree has a space complexity of O(n) and can perform both queries and updates in O(log n) time complexity.

Basic Properties

• Low-level indexing: A Fenwick Tree is indexed starting from 1, rather than 0 like an array.
• Cumulative sums: Each node in the Fenwick Tree stores the cumulative sum of a range of elements.
• Prefix sum: The cumulative sum from the start of the array to a given index can be calculated efficiently using the Fenwick Tree.

1// Fenwick Tree code here

xxxxxxxxxx

#include <iostream>

​

int main() {

  // Fenwick Tree code here

  return 0;

}

Building a Fenwick Tree

To build a Fenwick Tree, we need to follow the following steps:

1. Create an integer array bit of size n + 1, where n is the number of elements in the original array.
2. Initialize all elements of the bit array to 0 using a loop.
3. Update the Fenwick Tree using all elements of the original array using a loop.
4. Return the bit array, which is now a Fenwick Tree.

Here's the C++ code that demonstrates the implementation of building a Fenwick Tree:

1#include <iostream>
2using namespace std;
3
4// Function to update the value at a given index
5void update(int bit[], int n, int index, int value) {
6    index++;
7
8    while (index <= n) {
9        // Adding value to current index
10        bit[index] += value;
11
12        // Update index to its parent
13        index += index & -index;
14    }
15}
16
17// Function to get the prefix sum of elements up to a given index
18int getPrefixSum(int bit[], int index) {
19    index++;
20    int sum = 0;
21
22    while (index > 0) {
23        // Adding value at current index to sum
24        sum += bit[index];
25
26        // Update index to its parent
27        index -= index & -index;
28    }
29
30    return sum;
31}
32
33// Function to build a Fenwick Tree
34int* buildFenwickTree(int arr[], int n) {
35    // Creating a Fenwick Tree with n+1 elements
36    int* bit = new int[n + 1];
37
38    // Initializing all elements of the Fenwick Tree to 0
39    for (int i = 0; i <= n; i++) {
40        bit[i] = 0;
41    }
42
43    // Updating the Fenwick Tree using all elements of the array
44    for (int i = 0; i < n; i++) {
45        update(bit, n, i, arr[i]);
46    }
47
48    // Returning the Fenwick Tree
49    return bit;
50}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Function to update the value at a given index

void update(int bit[], int n, int index, int value) {

    index++;

​

    while (index <= n) {

        // Adding value to current index

        bit[index] += value;

​

        // Update index to its parent

        index += index & -index;

    }

}

​

// Function to get the prefix sum of elements up to a given index

int getPrefixSum(int bit[], int index) {

    index++;

    int sum = 0;

​

    while (index > 0) {

        // Adding value at current index to sum

        sum += bit[index];

​

        // Update index to its parent

        index -= index & -index;

    }

​

Querying a Fenwick Tree

After building a Fenwick Tree, we can perform queries on it efficiently. The Fenwick Tree allows us to calculate the prefix sum of a range of elements in O(log n) time, where n is the number of elements in the original array.

To query the Fenwick Tree, we need to follow these steps:

1. Initialize a variable sum with 0.
2. Traverse the tree in a bottom-up manner, starting from the given index.
3. In each step, add the value at the current index to sum.
4. Update the index to its parent index by removing the value of the rightmost set bit.
5. Repeat steps 3 to 4 until the index becomes 0.
6. Return the value of sum, which represents the prefix sum of the range of elements.

Let's see an example of how to query a Fenwick Tree in C++:

1#include <iostream>
2using namespace std;
3
4// Function to query the prefix sum of elements up to a given index
5int getPrefixSum(int bit[], int index) {
6    index++;
7    int sum = 0;
8
9    while (index > 0) {
10        // Adding value at current index to sum
11        sum += bit[index];
12
13        // Update index to its parent
14        index -= index & -index;
15    }
16
17    return sum;
18}
19
20// Usage
21int main() {
22    int arr[] = {1, 3, 2, -5, 4, 6};
23    int n = sizeof(arr) / sizeof(arr[0]);
24    int* bit = buildFenwickTree(arr, n);
25
26    // Query the prefix sum of the range [2, 4]
27    int prefixSum = getPrefixSum(bit, 4) - getPrefixSum(bit, 1);
28
29    cout << "Prefix Sum: " << prefixSum << endl;
30
31    return 0;
32}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Function to query the prefix sum of elements up to a given index

int getPrefixSum(int bit[], int index) {

    index++;

    int sum = 0;

​

    while (index > 0) {

        // Adding value at current index to sum

        sum += bit[index];

​

        // Update index to its parent

        index -= index & -index;

    }

​

    return sum;

}

​

// Usage

int main() {

    int arr[] = {1, 3, 2, -5, 4, 6};

    int n = sizeof(arr) / sizeof(arr[0]);

    int* bit = buildFenwickTree(arr, n);

​

    // Query the prefix sum of the range [2, 4]

    int prefixSum = getPrefixSum(bit, 4) - getPrefixSum(bit, 1);

​

    cout << "Prefix Sum: " << prefixSum << endl;

Updating a Fenwick Tree

Once a Fenwick Tree is built, we can perform updates on it efficiently. Updating a Fenwick Tree involves modifying the values of the original array and recalculating the prefix sum values for the affected elements.

To update a Fenwick Tree, we need to follow these steps:

1. Find the index of the element in the original array that needs to be updated.
2. Calculate the difference between the new value and the current value at that index.
3. Update the element in the original array with the new value.
4. Traverse the Fenwick Tree in a bottom-up manner, starting from the given index.
5. In each step, add the calculated difference to the value at the current index.
6. Update the index to its parent index by adding the value of the rightmost set bit.
7. Repeat steps 5 to 6 until the index becomes equal to or greater than the size of the Fenwick Tree.

Let's see an example of how to perform an update on a Fenwick Tree in C++:

1#include <iostream>
2using namespace std;
3
4// Function to update the value of an element in the original array
5void updateValue(int arr[], int bit[], int n, int index, int newValue) {
6    // Calculate the difference between new and current values
7    int difference = newValue - arr[index];
8    // Update the element in the original array
9    arr[index] = newValue;
10
11    index++;
12    // Traverse the Fenwick Tree and update the values
13    while (index <= n) {
14        bit[index] += difference;
15        index += index & -index;
16    }
17}
18
19// Usage
20int main() {
21    int arr[] = {1, 3, 2, -5, 4, 6};
22    int n = sizeof(arr) / sizeof(arr[0]);
23    int* bit = buildFenwickTree(arr, n);
24
25    // Update the value at index 3 to 8
26    updateValue(arr, bit, n, 3, 8);
27
28    cout << "Updated Array: ";
29    for (int i = 0; i < n; i++) {
30        cout << arr[i] << " ";
31    }
32    cout << endl;
33
34    return 0;
35}

Fenwick Tree Use Cases

Fenwick Trees, also known as Binary Indexed Trees (BIT), have several applications due to their efficient operations. Let's explore some common use cases where Fenwick Trees can be applied:

1. Prefix Sum Queries: Fenwick Trees are commonly used to calculate prefix sum queries efficiently. The prefix sum of an array at a given index is the sum of all elements from index 0 to that index. With Fenwick Trees, we can calculate prefix sums in O(logN) time complexity.

2. Range Sum Queries: Fenwick Trees can efficiently calculate the sum of elements in a given range [l, r] in an array. By taking the prefix sum of the right endpoint and subtracting the prefix sum of the left endpoint, we obtain the sum of elements in the specified range in O(logN) time complexity.

3. Single Element Updates: Fenwick Trees allow for efficient updates on a single element in the original array. By updating the affected prefix sums, we can maintain accurate prefix sum values throughout the Fenwick Tree without recalculating the entire sum.

4. Finding the Kth Smallest Element: Fenwick Trees can be used to find the Kth smallest element in an array efficiently. By using the binary search technique with prefix sums, we can determine the value at the Kth position in O(logN) time complexity.

These are just a few examples of how Fenwick Trees can be applied in various scenarios. Their efficient operations make them a valuable data structure for solving a wide range of problems.

Let's see an example of how Fenwick Trees can be used to calculate prefix sum queries in C++:

1#include <iostream>
2
3// Function to calculate the sum of elements from index 0 to a given index
4int getPrefixSum(int bit[], int index) {
5  int sum = 0;
6  index++;
7
8  // Traverse the Fenwick Tree in a bottom-up manner
9  while (index > 0) {
10    sum += bit[index];
11    index -= index & -index;
12  }
13
14  return sum;
15}
16
17// Function to update the value at a given index in the Fenwick Tree
18void updateValue(int bit[], int n, int index, int value) {
19  index++;
20
21  // Traverse the Fenwick Tree in a top-down manner
22  while (index <= n) {
23    bit[index] += value;
24    index += index & -index;
25  }
26}
27
28int main() {
29  int arr[] = {1, 3, 2, -5, 4, 6};
30  int n = sizeof(arr) / sizeof(arr[0]);
31  int bit[n+1] = {0};
32
33  // Build the Fenwick Tree
34  for (int i = 0; i < n; i++) {
35    updateValue(bit, n, i, arr[i]);
36  }
37
38  // Calculate prefix sum queries
39  int prefixSum = getPrefixSum(bit, 4);
40
41  std::cout << "Prefix Sum of elements from index 0 to 4: " << prefixSum << std::endl;
42
43  return 0;
44}

xxxxxxxxxx

#include <iostream>

​

int main() {

  // Code block here

  return 0;

}

Optimizations and Advanced Techniques

Fenwick Trees provide an efficient solution for various problems, but there are several optimizations and advanced techniques that can further enhance their performance and functionality. Let's explore some of these techniques:

1. Range Updates: Fenwick Trees can be modified to support range updates efficiently, where a range of values is incremented or decremented by a given amount. By maintaining two Fenwick Trees, one for prefix sums and another for updates, we can perform range updates in O(logN) time complexity.

2. Binary Lifting: Binary Lifting is a powerful technique that can be applied to optimize queries on Fenwick Trees. It involves precomputing and storing additional information in the Fenwick Tree such as the parent of each node, allowing for faster traversal and query operations.

3. Persistent Fenwick Trees: Persistent Fenwick Trees enable us to efficiently maintain historical versions of the Fenwick Tree. This can be useful in scenarios where we need to query the data structure at different points in time or undo specific updates.

These are just a few examples of the advanced techniques and optimizations that can be applied to Fenwick Trees. By understanding and implementing these techniques, you can further improve the performance and versatility of Fenwick Trees in your applications.

Let's see an example of how Binary Lifting can be applied to optimize queries on a Fenwick Tree in C++:

1#include <iostream>
2#include <vector>
3
4// Function to query the prefix sum from index 0 to a given index using Binary Lifting
5int queryPrefixSum(std::vector<int>& bit, int index) {
6  int sum = 0;
7
8  // Traverse the Fenwick Tree in a top-down manner
9  for (int i = 20; i >= 0; i--) {
10    int curr = sum + (1 << i);
11    if (curr <= index) {
12      sum = curr;
13      index -= (1 << i);
14    }
15  }
16
17  return sum;
18}
19
20int main() {
21  std::vector<int> arr = {1, 5, 2, 4, 3};
22  int n = arr.size();
23  std::vector<int> bit(n+1, 0);
24
25  // Build the Fenwick Tree
26  for (int i = 0; i < n; i++) {
27    for (int j = i+1; j = n; j += (j & -j)) {
28      bit[j] += arr[i];
29    }
30  }
31
32  // Query prefix sums using Binary Lifting
33  int prefixSum = queryPrefixSum(bit, 4);
34
35  std::cout << "Prefix Sum of elements from index 0 to 4: " << prefixSum << std::endl;
36
37  return 0;
38}

Conclusion

In this tutorial, we have covered the fundamental concepts and operations of Fenwick Trees. Let's summarize the key takeaways:

1. Fenwick Trees, also known as Binary Indexed Trees, provide an efficient data structure for prefix sum queries on an array of values.

2. Fenwick Trees can be built and updated in O(logN) time complexity, and can perform prefix sum queries in O(logN) time complexity.

3. The main advantage of Fenwick Trees over other data structures, such as segment trees, is their simplicity and memory efficiency.

4. Fenwick Trees can be applied to solve a variety of problems, including range queries, frequency counting, and inversion counting.

5. Advanced techniques and optimizations, such as range updates, binary lifting, and persistent Fenwick Trees, can further enhance the performance and versatility of Fenwick Trees.

By understanding and applying the concepts covered in this tutorial, you now have a strong foundation in Fenwick Trees and can utilize them effectively in problem-solving.