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;

    }

};