Binary Indexed Tree : Range Updates and Point Queries | C # code to demonstrate Range Update and * Point Queries on a Binary Index Tree . * This method only works when all array * values are initially 0. ; Max tree size ; 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 BITree ; Update index to that of parent in update View ; Constructs Binary Indexed Tree for given array of size n . ; 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 [ ] ; Initialize 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 Code ; 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
using System ; public class GFG { public const int MAX = 1000 ; public static int [ ] BITree = new int [ MAX ] ; public static void updateBIT ( int n , int index , int val ) { index = index + 1 ; while ( index <= n ) { BITree [ index ] += val ; index += index & ( - index ) ; } } public static void constructBITree ( int [ ] arr , int n ) { for ( int i = 1 ; i <= n ; i ++ ) { BITree [ i ] = 0 ; } for ( int i = 0 ; i < n ; i ++ ) { updateBIT ( n , i , arr [ i ] ) ; } } public static int getSum ( int index ) { int sum = 0 ; index = index + 1 ; while ( index > 0 ) { sum += BITree [ index ] ; index -= index & ( - index ) ; } return sum ; } public static void update ( int l , int r , int n , int val ) { updateBIT ( n , l , val ) ; updateBIT ( n , r + 1 , - val ) ; } public static void Main ( string [ ] args ) { int [ ] arr = new int [ ] { 0 , 0 , 0 , 0 , 0 } ; int n = arr . Length ; constructBITree ( arr , n ) ; int l = 2 , r = 4 , val = 2 ; update ( l , r , n , val ) ; int index = 4 ; Console . WriteLine ( " Element ▁ at ▁ index ▁ " + index + " ▁ is ▁ " + getSum ( index ) ) ; l = 0 ; r = 3 ; val = 4 ; update ( l , r , n , val ) ; index = 3 ; Console . WriteLine ( " Element ▁ at ▁ index ▁ " + index + " ▁ is ▁ " + getSum ( index ) ) ; } }