Topcoder Fenwick Tree Code Example
Example: 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 su