Fenwick Tree

Created

Jul 11, 2025

Last Modified

2 weeks ago

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<int> tree;
    int n;
public:
    FenwickTree(const vector<int> &nums){
        this->n = nums.size() + 1; // 1 based indexing
        tree.resize(n);
        for(int i = 1; i<n; ++i){
            update(i, nums[i-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;
    }
    int rangeSum(int left, int right){
        return query(right) - query(left - 1);
    }
};

307. Range Sum Query - Mutable

cpp

class NumArray {
    vector<int> 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<int>& 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<int> 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<int> 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<int> countSmaller(vector<int>& nums) {
        // compress the num [each num will be an index]
        set<int> sorted(nums.begin(), nums.end());
        unordered_map<int, int> rank;
        int index = 1;
        for(auto &num : sorted){
            rank[num] = index++;
        }

        FenwickTree ft(1e5 + 7);
        vector<int> 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;
    }
};