binary indexed tree

1template<class T> class BIT {
2
3    vector<T> bit;
4public:
5    BIT (int size) : bit(vector<T>(size+1)) {}
6    BIT (vector<T>& v) : bit(vector<T>(v.size()+1)) {
7        for (int i = 0; i<v.size(); ++i) {
8            update(i, v[i]);
9        }
10    }
11    T sum (int i) {
12        ++i;
13        T s = 0;
14        while (i>0) {
15            s += bit[i];
16            i -= i&-i;
17        }
18        return s;
19    }
20    void update (int i, T u) {
21        ++i;
22        while (i<bit.size()) {
23            bit[i] += u;
24            i += i&-i;
25        }
26    }
27
28};

1// C++ code to demonstrate operations of Binary Index Tree 
2#include <iostream> 
3  
4using namespace std; 
5  
6/*         n --> No. of elements present in input array.  
7    BITree[0..n] --> Array that represents Binary Indexed Tree. 
8    arr[0..n-1] --> Input array for which prefix sum is evaluated. */
9  
10// Returns sum of arr[0..index]. This function assumes 
11// that the array is preprocessed and partial sums of 
12// array elements are stored in BITree[]. 
13int getSum(int BITree[], int index) 
14{ 
15    int sum = 0; // Iniialize result 
16  
17    // index in BITree[] is 1 more than the index in arr[] 
18    index = index + 1; 
19  
20    // Traverse ancestors of BITree[index] 
21    while (index>0) 
22    { 
23        // Add current element of BITree to sum 
24        sum += BITree[index]; 
25  
26        // Move index to parent node in getSum View 
27        index -= index & (-index); 
28    } 
29    return sum; 
30} 
31  
32// Updates a node in Binary Index Tree (BITree) at given index 
33// in BITree. The given value 'val' is added to BITree[i] and  
34// all of its ancestors in tree. 
35void updateBIT(int BITree[], int n, int index, int val) 
36{ 
37    // index in BITree[] is 1 more than the index in arr[] 
38    index = index + 1; 
39  
40    // Traverse all ancestors and add 'val' 
41    while (index <= n) 
42    { 
43    // Add 'val' to current node of BI Tree 
44    BITree[index] += val; 
45  
46    // Update index to that of parent in update View 
47    index += index & (-index); 
48    } 
49} 
50  
51// Constructs and returns a Binary Indexed Tree for given 
52// array of size n. 
53int *constructBITree(int arr[], int n) 
54{ 
55    // Create and initialize BITree[] as 0 
56    int *BITree = new int[n+1]; 
57    for (int i=1; i<=n; i++) 
58        BITree[i] = 0; 
59  
60    // Store the actual values in BITree[] using update() 
61    for (int i=0; i<n; i++) 
62        updateBIT(BITree, n, i, arr[i]); 
63  
64    // Uncomment below lines to see contents of BITree[] 
65    //for (int i=1; i<=n; i++) 
66    //     cout << BITree[i] << " "; 
67  
68    return BITree; 
69} 
70  
71  
72// Driver program to test above functions 
73int main() 
74{ 
75    int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; 
76    int n = sizeof(freq)/sizeof(freq[0]); 
77    int *BITree = constructBITree(freq, n); 
78    cout << "Sum of elements in arr[0..5] is "
79        << getSum(BITree, 5); 
80  
81    // Let use test the update operation 
82    freq[3] += 6; 
83    updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[] 
84  
85    cout << "\nSum of elements in arr[0..5] after update is "
86        << getSum(BITree, 5); 
87  
88    return 0; 
89}