Binary Indexed Tree - Code in C++

 // C++ code to demonstrate operations of Binary Index Tree  
 #include <iostream>  
 using namespace std;  
 int getSum(int BITree[], int n, 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  
           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  
      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]);  
      return BITree;  
 }  
 // Driver program to test above functions  
 int main()  
 {  
      int *freq,n;                     
      cout<<"enter number of elements: ";  
      cin>>n;  
      freq = new int[n];  
      cout<<"enter the array elements : \n";  
      for(int i=0;i<n;i++)  
       cin>>freq[i];         //check on this to validate above figure {3,5,1,6,7,2,3,4,1,9,13,8};  
      int *BITree = constructBITree(freq, n);  
      //for(int i=1;i<=n;i++)cout<<BITree[i]<<" ";  //uncomment this line to content of BITree[]  
      cout << "Sum of elements in arr[0..5] is "  
           << getSum(BITree, n, 5);  
      // Let use test the update operation  
      int id,value;  
      cout<<"\nenter index and value to be updated : ";  
       cin>>id>>value;  
      updateBIT(BITree, n, id, value); //Update BIT for above change in arr[]  
      cout << "\nSum of elements in arr[0..5] after update is "  
           << getSum(BITree, n, 5);  
      return 0;  
 }