Introduction to Fenwick Tree

Fenwick Tree, also known as Binary Indexed Tree (BIT), is a data structure that allows efficient updates and range queries. It is often used when we need to update and retrieve prefix sums of an array.

Properties of Fenwick Tree

• The Fenwick Tree is represented by an array of values called BIT.
• The size of the BIT array is one more than the size of the input array.
• Each value in the BIT array represents the sum of a specific range of values in the input array.
• The value at index i in the BIT array is the sum of all elements from index i - 2^r + 1 to index i, where r is the position of the rightmost set bit in the binary representation of i.

Key Operations

The Fenwick Tree supports two main operations:

1. Update: It allows updating the value of an element in the input array with a given increment or decrement.
2. Query: It allows calculating the sum of elements in a given range from index 1 to i.

Let's take a look at an example C++ implementation of the Fenwick Tree:

xxxxxxxxxx

}

// Fenwick Tree implementation

#include <iostream>

#include <vector>

using namespace std;

​

class FenwickTree {

private:

    vector<int> BIT;

public:

    FenwickTree(int n) {

        BIT.resize(n + 1, 0);

    }

​

    void update(int idx, int val) {

        while (idx < BIT.size()) {

            BIT[idx] += val;

            idx += (idx & -idx);

        }

    }

​

    int query(int idx) {

        int sum = 0;

        while (idx > 0) {

            sum += BIT[idx];

            idx -= (idx & -idx);

        }

        return sum;

    }

};

Creating a Fenwick Tree

To create a Fenwick Tree, we need to implement the necessary methods: update and query.

The update method is used to update the value of an element in the Fenwick Tree. It takes two parameters: index and value. Starting from the given index, we update the corresponding values in the tree by adding the value. We continue updating until we reach the end of the tree or go out of bounds.

Here's an example of how to implement the update method in C++:

1void update(int index, int value) {
2  while (index < tree.size()) {
3    tree[index] += value;
4    index += index & (-index);
5  }
6}

The query method is used to calculate the sum of elements in a given range from index 1 to the given index. It takes one parameter: index. Starting from the given index, we calculate the sum by iterating through the tree, adding the values at each index. We continue iterating until we reach 0.

Here's an example of how to implement the query method in C++:

1int query(int index) {
2  int sum = 0;
3  while (index > 0) {
4    sum += tree[index];
5    index -= index & (-index);
6  }
7  return sum;
8}

Let's create a Fenwick Tree with a size of 10 and perform an update operation at index 5 with a value of 3. Then, we'll perform a query operation at index 8 and print the result:

xxxxxxxxxx

}

#include <iostream>

#include <vector>

​

class FenwickTree {

  std::vector<int> tree;

​

public:

  FenwickTree(int n) {

    tree.resize(n + 1, 0);

  }

​

  void update(int index, int value) {

    while (index < tree.size()) {

      tree[index] += value;

      index += index & (-index);

    }

  }

​

  int query(int index) {

    int sum = 0;

    while (index > 0) {

      sum += tree[index];

      index -= index & (-index);

    }

    return sum;

  }

};

​

int main() {

Updating a Fenwick Tree

To update the value of an element in a Fenwick Tree, we can use the update method. This method takes two parameters: index and value. Starting from the given index, we update the corresponding values in the tree by adding the value. We continue updating until we reach the end of the tree or go out of bounds.

Here's an example of how to implement the update method in C++:

1void update(int index, int value) {
2  while (index < tree.size()) {
3    tree[index] += value;
4    index += index & (-index);
5  }
6}

In the above code, we iterate through the tree starting from the given index and update the values by adding the value. We update the index by adding the least significant bit (obtained by using the & operator with the two's complement of the index). This process continues until we reach the end of the tree or go out of bounds.

Let's create a Fenwick Tree with a size of 10 and perform an update operation at index 5 with a value of 3. Then, we'll perform a query operation at index 8 and print the result.

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Class for Fenwick Tree

class FenwickTree {

private:

  vector<int> tree;

public:

  // Constructor

  FenwickTree(int size) {

    tree.resize(size + 1, 0);

  }

​

  // Update method

  void update(int index, int value) {

    while (index < tree.size()) {

      tree[index] += value;

      index += index & (-index);

    }

  }

​

  // Query method

  int query(int index) {

    int sum = 0;

    while (index > 0) {

      sum += tree[index];

      index -= index & (-index);

    }

    return sum;

Querying a Fenwick Tree

To answer range sum queries on a Fenwick Tree, we can use the query method. This method takes one parameter: the index of the element up to which we want to calculate the sum. Starting from the given index, we traverse the Fenwick Tree by moving to the parent node until we reach the root or go out of bounds. At each node, we add the value stored at that node to the running sum. Finally, we return the sum as the result of the query.

Here's an example of how to implement the query method in C++:

1int query(int index, vector<int>& tree) {
2  int sum = 0;
3
4  while (index > 0) {
5    sum += tree[index];
6
7    // Move to the parent
8    index -= index & (-index);
9  }
10
11  return sum;
12}

In the above code, we start with a sum of 0 and iterate through the tree starting from the given index. At each node, we add the value stored at that node to the sum. We then move to the parent node by subtracting the least significant bit (obtained by using the & operator with the two's complement of the index). This process continues until we reach the root of the tree or go out of bounds.

Let's create a Fenwick Tree with a size of 11 and perform some update operations. Then, we'll perform a query operation at index 10 to calculate the sum of all elements up to that index and print the result.

xxxxxxxxxx

}

#include <iostream>

#include <vector>

​

using namespace std;

​

// Querying a Fenwick Tree

​

int query(int index, vector<int>& tree) {

  int sum = 0;

​

  while (index > 0) {

    sum += tree[index];

​

    // Move to the parent

    index -= index & (-index);

  }

​

  return sum;

}

​

int main() {

  // Create a Fenwick Tree

  vector<int> tree(11, 0);

​

  // Update elements

  tree[3] += 5;

  tree[6] += 9;

  tree[8] += 2;

  tree[9] += 7;

Advanced Operations

Fenwick Trees not only support basic operations like creating, updating, and querying the sum of elements, but they also provide more advanced operations for efficient range updates and point updates.

Range Updates

Range updates allow us to update a range of elements in the Fenwick Tree efficiently with a single operation. To perform a range update, we need to update multiple elements in the range using their corresponding update values. The update values are usually obtained through pre-processing, such as taking the difference between consecutive elements in the original array.

Here's an example of how to implement a range update operation in C++:

1void rangeUpdate(int left, int right, int value, vector<int>& tree) {
2  update(left, value, tree);
3  update(right + 1, -value, tree);
4}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Fenwick Tree class

class FenwickTree {

private:

  vector<int> tree;

​

public:

  FenwickTree(int size) {

    tree.resize(size + 1);

  }

​

  void update(int index, int value) {

    while (index < tree.size()) {

      tree[index] += value;

      index += index & (-index);

    }

  }

​

  int prefixSum(int index) {

    int sum = 0;

    while (index > 0) {

      sum += tree[index];

      index -= index & (-index);

    }

    return sum;

  }

​

Applications of Fenwick Tree

Fenwick Trees find use in a wide range of applications. Here are a few notable ones:

• Range Sum Queries: Fenwick Trees can efficiently answer range sum queries on arrays or sequences. They provide a flexible and efficient way to calculate and update the sum of elements in a given range.

• Inversion Count: Inversion count is the measure of how far an array is from being sorted. Fenwick Trees can be used to efficiently calculate the inversion count of an array, making it useful in sorting and ranking problems.

• Frequency Count: Fenwick Trees can also be used to efficiently count the frequency of occurrences of elements in an array or a sequence. This is particularly useful in problems where you need to track the frequency of elements as you traverse the array.

Do you want to see an example of how a Fenwick Tree can be implemented in C++ to update values and calculate prefix sums?

xxxxxxxxxx

#include <iostream>

using namespace std;

​

int main() {

  // Fenwick Tree implementation

  int n = 10;

  int fenwickTree[11] = {0};

​

  // Update value at index

  int indexToUpdate = 5;

  int valueToUpdate = 8;

  while (indexToUpdate <= n) {

    fenwickTree[indexToUpdate] += valueToUpdate;

    indexToUpdate += indexToUpdate & -indexToUpdate;

  }

​

  // Get prefix sum

  int prefixSum = 0;

  int index = 10;

  while (index > 0) {

    prefixSum += fenwickTree[index];

    index -= index & -index;

  }

​

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

​

  return 0;

}