Array range queries over range queries | Java program to perform range queries over range queries . ; 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 ; Returns sum of arr [ 0. . index ] . This function assumes that the array is preprocessed and partial sums of array elements are stored in BITree [ ] ; index in BITree [ ] is 1 more than the index in arr [ ] ; Traverse ancestors of BITree [ index ] ; Add element of BITree to sum ; Move index to parent node in getSum View ; Function to update the BITree ; Driver code ; BITree for query of type 2 ; BITree for query of type 1 ; Input the queries in a 2D matrix ; If query is of type 2 then function call to update with BITree ; If query is of type 1 then function call to update with BITree2
import java . io . * ; import java . util . * ; class GFG { static void updateBIT ( int BITree [ ] , int n , int index , int val ) { index = index + 1 ; while ( index <= n ) { BITree [ index ] = ( val + BITree [ index ] ) ; index = ( index + ( index & ( - index ) ) ) ; } return ; } static int [ ] constructBITree ( int n ) { int [ ] BITree = new int [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; return BITree ; } static int getSum ( int BITree [ ] , int index ) { int sum = 0 ; index = index + 1 ; while ( index > 0 ) { sum = ( sum + BITree [ index ] ) ; index -= index & ( - index ) ; } return sum ; } static void update ( int BITree [ ] , int l , int r , int n , int val ) { updateBIT ( BITree , n , l , val ) ; updateBIT ( BITree , n , r + 1 , - val ) ; return ; } public static void main ( String [ ] args ) { int n = 5 , m = 5 ; int temp [ ] = { 1 , 1 , 2 , 1 , 4 , 5 , 2 , 1 , 2 , 2 , 1 , 3 , 2 , 3 , 4 } ; int [ ] [ ] q = new int [ 6 ] [ 3 ] ; int j = 0 ; for ( int i = 1 ; i <= m ; i ++ ) { q [ i ] [ 0 ] = temp [ j ++ ] ; q [ i ] [ 1 ] = temp [ j ++ ] ; q [ i ] [ 2 ] = temp [ j ++ ] ; } int [ ] BITree = constructBITree ( m ) ; int [ ] BITree2 = constructBITree ( n ) ; Scanner sc = new Scanner ( System . in ) ; for ( int i = 1 ; i <= m ; i ++ ) { q [ i ] [ 0 ] = sc . nextInt ( ) ; q [ i ] [ 1 ] = sc . nextInt ( ) ; q [ i ] [ 2 ] = sc . nextInt ( ) ; } for ( int i = m ; i >= 1 ; i -- ) if ( q [ i ] [ 0 ] == 2 ) update ( BITree , q [ i ] [ 1 ] - 1 , q [ i ] [ 2 ] - 1 , m , 1 ) ; for ( int i = m ; i >= 1 ; i -- ) { if ( q [ i ] [ 0 ] == 2 ) { int val = getSum ( BITree , i - 1 ) ; update ( BITree , q [ i ] [ 1 ] - 1 , q [ i ] [ 2 ] - 1 , m , val ) ; } } for ( int i = m ; i >= 1 ; i -- ) { if ( q [ i ] [ 0 ] == 1 ) { int val = getSum ( BITree , i - 1 ) ; update ( BITree2 , q [ i ] [ 1 ] - 1 , q [ i ] [ 2 ] - 1 , n , ( val + 1 ) ) ; } } for ( int i = 1 ; i <= n ; i ++ ) System . out . print ( getSum ( BITree2 , i - 1 ) + " ▁ " ) ; } }