Binary Indexed Tree : Range Updates and Point Queries | C ++ code to demonstrate Range Update and Point Queries on a Binary Index Tree ; 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 . ; index in BITree [ ] is 1 more than the index in arr [ ] ; Traverse all ancestors and add ' val ' ; Add ' val ' to current node of BI Tree ; Update index to that of parent in update View ; Constructs and returns a Binary Indexed Tree for given array of size n . ; Create and initialize BITree [ ] as 0 ; Store the actual values in BITree [ ] using update ( ) ; SERVES THE PURPOSE OF getElement ( ) Returns sum of arr [ 0. . index ] . This function assumes that the array is preprocessed and partial sums of array elements are stored in BITree [ ] ; Iniialize result ; index in BITree [ ] is 1 more than the index in arr [ ] ; Traverse ancestors of BITree [ index ] ; Add current element of BITree to sum ; Move index to parent node in getSum View ; Return the sum ; Updates such that getElement ( ) gets an increased value when queried from l to r . ; Increase value at ' l ' by ' val ' ; Decrease value at ' r + 1' by ' val ' ; Driver program to test above function ; Add 2 to all the element from [ 2 , 4 ] ; Find the element at Index 4 ; Add 2 to all the element from [ 0 , 3 ] ; Find the element at Index 3
#include <bits/stdc++.h> NEW_LINE using namespace std ; void updateBIT ( int BITree [ ] , int n , int index , int val ) { index = index + 1 ; while ( index <= n ) { BITree [ index ] += val ; index += index & ( - index ) ; } } int * constructBITree ( int arr [ ] , int n ) { int * BITree = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) updateBIT ( BITree , n , i , arr [ i ] ) ; return BITree ; } int getSum ( int BITree [ ] , int index ) { int sum = 0 ; index = index + 1 ; while ( index > 0 ) { sum += BITree [ index ] ; index -= index & ( - index ) ; } return sum ; } void update ( int BITree [ ] , int l , int r , int n , int val ) { updateBIT ( BITree , n , l , val ) ; updateBIT ( BITree , n , r + 1 , - val ) ; } int main ( ) { int arr [ ] = { 0 , 0 , 0 , 0 , 0 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int * BITree = constructBITree ( arr , n ) ; int l = 2 , r = 4 , val = 2 ; update ( BITree , l , r , n , val ) ; int index = 4 ; cout << " Element ▁ at ▁ index ▁ " << index << " ▁ is ▁ " << getSum ( BITree , index ) << " STRNEWLINE " ; l = 0 , r = 3 , val = 4 ; update ( BITree , l , r , n , val ) ; index = 3 ; cout << " Element ▁ at ▁ index ▁ " << index << " ▁ is ▁ " << getSum ( BITree , index ) << " STRNEWLINE " ; return 0 ; }