Sum of product of all unordered pairs in given range with update queries | Java Program for the above approach ; Vector to store fenwick tree of the 1 st type ; Vector to store fenwick tree of the 2 nd type ; Function to update the value at idx index in fenwick tree ; Function to return the sum of values stored from O to idx index in the array using Fenwick Tree ; Function to build the Fenwick tree from the a [ ] Array ; Function call to update the ith element in the first Fenwick Tree ; Function call to update the ith element in the first Fenwick Tree ; Function to find the Pairwise Product Sum in the range L to R ; Function call to calculate E in the given range ; Function call to calculate E in the given range ; Print Answer ; Function to update the Fenwick tree and the array element at index P to the new value X ; Function call to update the value in 1 st Fenwick Tree ; Function call to update the value in 2 nd Fenwick Tree ; Function to solve Q queries ; Function Call to build the Fenwick Tree ; If Query is of type 1 ; If Query is of type 2 ; Driver Code
class GFG { static final int MAXN = 100000 ; static int [ ] bit1 = new int [ MAXN ] ; static int [ ] bit2 = new int [ MAXN ] ; static void update ( int idx , int val , int [ ] bit ) { while ( idx < bit . length ) { bit [ idx ] += val ; idx += idx & ( - idx ) ; } } static int query ( int idx , int [ ] bit ) { int res = 0 ; while ( idx > 0 ) { res += bit [ idx ] ; idx -= idx & ( - idx ) ; } return res ; } static void buildFenwickTree ( int a [ ] , int n ) { for ( int i = 1 ; i <= n ; i ++ ) { update ( i , a [ i - 1 ] , bit1 ) ; update ( i , a [ i - 1 ] * a [ i - 1 ] , bit2 ) ; } } static void pairwiseProductSum ( int a [ ] , int l , int r ) { int sum , e , q ; e = query ( r , bit1 ) - query ( l - 1 , bit1 ) ; e = e * e ; q = query ( r , bit2 ) - query ( l - 1 , bit2 ) ; sum = ( e - q ) / 2 ; System . out . print ( sum + "NEW_LINE"); } static void updateArray ( int [ ] a , int p , int x ) { update ( p , - a [ p - 1 ] , bit1 ) ; update ( p , x , bit1 ) ; update ( p , - a [ p - 1 ] * a [ p - 1 ] , bit2 ) ; update ( p , x * x , bit2 ) ; a [ p - 1 ] = x ; } static void solveQueries ( int [ ] a , int n , int Q , int query [ ] [ ] ) { buildFenwickTree ( a , n ) ; for ( int i = 0 ; i < Q ; i ++ ) { if ( query [ i ] [ 0 ] == 1 ) pairwiseProductSum ( a , query [ i ] [ 1 ] , query [ i ] [ 2 ] ) ; else updateArray ( a , query [ i ] [ 1 ] , query [ i ] [ 2 ] ) ; } } public static void main ( String [ ] args ) { int A [ ] = { 5 , 7 , 2 , 3 , 1 } ; int N = A . length ; int Q = 3 ; int query [ ] [ ] = { { 1 , 1 , 3 } , { 2 , 2 , 5 } , { 1 , 2 , 5 } } ; solveQueries ( A , N , Q , query ) ; } }