binary indexed tree c++ code example

Example 1: binary index tree c++

class bit{
public:
    int n;
    vector<int> tree;

    bit(){};
    bit(int _n){
        n=_n;
        tree.resize(n+1);
    };

    void update(int idx,int val){
        while(idx<=n){
            tree[idx]+=val;
            idx+=idx&(-idx);
        }
    };

    int read(int idx){
        int res=0;
        while(idx>0){
            res+=tree[idx];
            idx-=idx&(-idx);
        }
        return res;
    };

    int sum(int L,int R){
        return read(R)-read(L-1);
    };
};

Example 2: binary indexed tree

template<class T> class BIT {

    vector<T> bit;
public:
    BIT (int size) : bit(vector<T>(size+1)) {}
    BIT (vector<T>& v) : bit(vector<T>(v.size()+1)) {
        for (int i = 0; i<v.size(); ++i) {
            update(i, v[i]);
        }
    }
    T sum (int i) {
        ++i;
        T s = 0;
        while (i>0) {
            s += bit[i];
            i -= i&-i;
        }
        return s;
    }
    void update (int i, T u) {
        ++i;
        while (i<bit.size()) {
            bit[i] += u;
            i += i&-i;
        }
    }

};

Example 3: dfenwick tree code c++

// C++ code to demonstrate operations of Binary Index Tree 
#include <iostream> 
  
using namespace std; 
  
/*         n --> No. of elements present in input array.  
    BITree[0..n] --> Array that represents Binary Indexed Tree. 
    arr[0..n-1] --> Input array for which prefix sum is evaluated. */
  
// Returns sum of arr[0..index]. This function assumes 
// that the array is preprocessed and partial sums of 
// array elements are stored in BITree[]. 
int getSum(int BITree[], int index) 
{ 
    int sum = 0; // Iniialize result 
  
    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1; 
  
    // Traverse ancestors of BITree[index] 
    while (index>0) 
    { 
        // Add current element of BITree to sum 
        sum += BITree[index]; 
  
        // Move index to parent node in getSum View 
        index -= index & (-index); 
    } 
    return sum; 
} 
  
// Updates a node in Binary Index Tree (BITree) at given index 
// in BITree. The given value 'val' is added to BITree[i] and  
// all of its ancestors in tree. 
void updateBIT(int BITree[], int n, int index, int val) 
{ 
    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1; 
  
    // Traverse all ancestors and add 'val' 
    while (index <= n) 
    { 
    // Add 'val' to current node of BI Tree 
    BITree[index] += val; 
  
    // Update index to that of parent in update View 
    index += index & (-index); 
    } 
} 
  
// Constructs and returns a Binary Indexed Tree for given 
// array of size n. 
int *constructBITree(int arr[], int n) 
{ 
    // Create and initialize BITree[] as 0 
    int *BITree = new int[n+1]; 
    for (int i=1; i<=n; i++) 
        BITree[i] = 0; 
  
    // Store the actual values in BITree[] using update() 
    for (int i=0; i<n; i++) 
        updateBIT(BITree, n, i, arr[i]); 
  
    // Uncomment below lines to see contents of BITree[] 
    //for (int i=1; i<=n; i++) 
    //     cout << BITree[i] << " "; 
  
    return BITree; 
} 
  
  
// Driver program to test above functions 
int main() 
{ 
    int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; 
    int n = sizeof(freq)/sizeof(freq[0]); 
    int *BITree = constructBITree(freq, n); 
    cout << "Sum of elements in arr[0..5] is "
        << getSum(BITree, 5); 
  
    // Let use test the update operation 
    freq[3] += 6; 
    updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[] 
  
    cout << "\nSum of elements in arr[0..5] after update is "
        << getSum(BITree, 5); 
  
    return 0; 
}