FenWick Tree

Fenwick Tree, also known as Binary Indexed Tree, is a powerful data structure designed to efficiently handle prefix sums and updates in logarithmic time. Instead of recomputing sums repeatedly, it cleverly uses binary representation and the least significant bit (LSB) to store partial results, allowing both queries and updates to run in O(log n). This makes it an essential tool for solving range query problems where performance truly matters.

You start at a given index and traverse downwards (toward index 0), repeatedly subtracting the Least Significant Bit (LSB) to move to the contributing children.

Fenwick Tree (Binary Indexed Tree) query operation showing how prefix sum is calculated by subtracting the least significant bit (LSB) and traversing parent ranges.

You start at a given index and traverse upwards (toward the end of the tree), repeatedly adding the Least Significant Bit (LSB) to move to the ancestor.

Fenwick Tree (Binary Indexed Tree) update operation demonstrating how values propagate upward using least significant bit (LSB) addition to update affected ranges.

✍️ Code: Build, Update, and Query

cpp

class FenwickTree{
    int LSB(int index){
        return index & (-index);
    }
    vector tree;
    int n;
public:
    FenwickTree(const vector &nums){
        this->n = nums.size() + 1; // 1 based indexing
        tree.resize(n);
        for(int i = 1; i 0){
            sum += tree[index];
            index -= LSB(index);
        }
        return sum;
    }
    int rangeSum(int left, int right){
        return query(right) - query(left - 1);
    }
};

307. Range Sum Query - Mutable

cpp

class NumArray {
    vector nums, tree;
    int treeSize;
    int LSB(int index){
        return index & (-index);
    }
    int prefixSum(int index){
        index++;
        int sum = 0;
        while(index > 0){
            sum += tree[index];
            index -= LSB(index);
        }
        return sum;
    }
    void updateTree(int index, int val){
        index++;
        while(index < treeSize){
            tree[index] += val;
            index += LSB(index);
        }
    }
public:
    NumArray(vector& nums) {
        this->nums = nums;
        treeSize = nums.size() + 1;
        tree.resize(treeSize, 0);

        for(int i = 0; i< nums.size(); ++i){
            updateTree(i, nums[i]);
        }
    }
    
    void update(int index, int val) {
        int newVal = val - nums[index];
        nums[index] = val;
        updateTree(index, newVal);
    }
    
    int sumRange(int left, int right) {
        return prefixSum(right) - prefixSum(left - 1);
    }
};

Frequency of each element

cpp

class FenwickTree{
    int LSB(int index){
        return index & (-index);
    }
    vector tree;
    int n;
public:
    FenwickTree(int n){
        this->n = n+1;
        tree.resize(n, 0);
    }

    int query(int index){
        int sum = 0;
        while(index > 0){
            sum += tree[index];
            index -= LSB(index);
        }
        return sum;
    }

    void update(int index, int value){
        while(index < n){
            tree[index] += value;
            index += LSB(index);
        }
    }

    int frequency(int index){
        return query(index) - query(index - 1);
    }
};

315. Count of Smaller Numbers After Self

cpp

class FenwickTree{
    int n;
    vector tree;
    int LSB(int index){
        return index & (-index);
    }
public:
    FenwickTree(int size){
        this->n = size + 1;
        tree.resize(n + 1);
    }

    void update(int index, int value){
        while(index < n){
            tree[index] += value;
            index += LSB(index);
        }
    }

    int query(int index){
        int sum = 0;
        while(index > 0){
            sum += tree[index];
            index -= LSB(index);
        }
        return sum;
    }
};
class Solution {
public:
    vector countSmaller(vector& nums) {
        // compress the num [each num will be an index]
        set sorted(nums.begin(), nums.end());
        unordered_map rank;
        int index = 1;
        for(auto &num : sorted){
            rank[num] = index++;
        }

        FenwickTree ft(1e5 + 7);
        vector result(nums.size());
        
        for(int i = nums.size() - 1; i>=0; --i){
            int num = nums[i];
            result[i] = ft.query(rank[num] - 1);
            ft.update(rank[num], 1);
        }
        return result;
    }
};