Given an array A[] consisting of N integers and Q queries of the below types, the task is to print the output for all the update queries.
- (1, L, R): The 1st type of query to find the sum of the product of all unordered pairs from index L to R in the array where 1 <= L <= R <= N.
- (2, P, X): The 2nd type of query to change the value of the Pth integer of the array to a new value X.
Example:
Input: A[] = {5 7 2 3 1}, Q = 3, Queries[] = [ [1, 1, 3], [2, 2, 5], [1, 2, 5]]
Output:
59
41
Explanation:
Query 1: In the 1st query, the possible pairs in the given range are (5, 7), (5, 2) and (7, 2). So the pairwise product sum will be (5*7) + (5*2) + (7*2) = 35 + 10 + 14 = 59.
Query 2: In the 2nd query, update the 2nd integer to 5, which makes the array as [5, 5, 2, 3, 1].
Query 3: In the 3rd query, the possible pairs in range [2, 5] are (5, 2), (5, 3), (5, 1), (2, 3), (2, 1), and (3, 1). The sum of product of these pairs is 41.Input: A[] = {7 3 2 1 4 5 8}, Q = 5, Queries[] = [ [1, 1, 6], [2, 2, 4], [1, 2, 5], [2, 3, 8], [1, 4, 7]]
Output: 59
41
6
Naive Approach: The simple way to solve this is to for the 1st type of query, generate all unordered pairs in the given range of query and print the sum of product of these pairs. For the 2nd type of queries, update the array element as per the given value.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the Pairwise// Product Sum in range from L to Rvoid pairwiseProductSum(int a[], int l, int r){ int sum = 0; // Loop to iterate over all possible // pairs from L to R for (int j = l - 1; j <= r - 1; j++) { for (int k = j + 1; k <= r - 1; k++) { sum += (a[j] * a[k]); } } // Print answer cout << sum << endl;}// Function to update the Array// element at index P to Xvoid updateArray(int* a, int p, int x){ // Update the value at Pth // index in the array a[p - 1] = x;}// Function to solve Q queriesvoid solveQueries( int* a, int n, int Q, int query[][3]){ for (int i = 0; i < Q; i++) { // If Query is of type 1 if (query[i][0] == 1) pairwiseProductSum( a, query[i][1], query[i][2]); // If Query is of type 2 else updateArray( a, query[i][1], query[i][2]); }}// Driver Codeint main(){ int A[] = { 5, 7, 2, 3, 1 }; int N = sizeof(A) / sizeof(int); int Q = 3; int query[Q][3] = { { 1, 1, 3 }, { 2, 2, 5 }, { 1, 2, 5 } }; solveQueries(A, N, Q, query); return 0;} |
Java
// Java Program for the above approachimport java.util.*;class GFG{// Function to calculate the Pairwise// Product Sum in range from L to Rstatic void pairwiseProductSum(int a[], int l, int r){ int sum = 0; // Loop to iterate over all possible // pairs from L to R for (int j = l - 1; j <= r - 1; j++) { for (int k = j + 1; k <= r - 1; k++) { sum += (a[j] * a[k]); } } // Print answer System.out.print(sum +"\n");}// Function to update the Array// element at index P to Xstatic void updateArray(int[] a, int p, int x){ // Update the value at Pth // index in the array a[p - 1] = x;}// Function to solve Q queriesstatic void solveQueries( int[] a, int n, int Q, int query[][]){ for (int i = 0; i < Q; i++) { // If Query is of type 1 if (query[i][0] == 1) pairwiseProductSum( a, query[i][1], query[i][2]); // If Query is of type 2 else updateArray( a, query[i][1], query[i][2]); }}// Driver Codepublic 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);}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 Program for the above approach# Function to calculate the Pairwise# Product Sum in range from L to Rdef pairwiseProductSum(a, l, r): sum = 0 # Loop to iterate over all possible # pairs from L to R for j in range(l - 1,r,1): for k in range(j + 1,r,1): sum += (a[j] * a[k]); # Print answer print(sum)# Function to update the Array# element at index P to Xdef updateArray(a, p, x): # Update the value at Pth # index in the array a[p - 1] = x# Function to solve Q queriesdef solveQueries(a,n,Q,query): for i in range(Q): # If Query is of type 1 if (query[i][0] == 1): pairwiseProductSum(a, query[i][1], query[i][2]) # If Query is of type 2 else: updateArray(a, query[i][1], query[i][2])# Driver Codeif __name__ == '__main__': A = [5, 7, 2, 3, 1] N = len(A) Q = 3 query = [[1, 1, 3],[2, 2, 5],[1, 2, 5]] solveQueries(A, N, Q, query) # This code is contributed by ipg2016107 |
C#
//C# code for the above approachusing System;public class GFG{// Function to calculate the Pairwise// Product Sum in range from L to Rstatic void pairwiseProductSum(int[] a, int l, int r){ int sum = 0; // Loop to iterate over all possible // pairs from L to R for (int j = l - 1; j <= r - 1; j++) { for (int k = j + 1; k <= r - 1; k++) { sum += (a[j] * a[k]); } } // Print answer Console.Write(sum +"\n");}// Function to update the Array// element at index P to Xstatic void updateArray(int[] a, int p, int x){ // Update the value at Pth // index in the array a[p - 1] = x;}// Function to solve Q queriesstatic void solveQueries( int[] a, int n, int Q, int[][] query){ for (int i = 0; i < Q; i++) { // If Query is of type 1 if (query[i][0] == 1) pairwiseProductSum( a, query[i][1], query[i][2]); // If Query is of type 2 else updateArray( a, query[i][1], query[i][2]); }}// Driver Code static public void Main (){ // Code int[] A = { 5, 7, 2, 3, 1 }; int N = A.Length; int Q = 3; int[][] query = { new int[3]{ 1, 1, 3 }, new int[3]{ 2, 2, 5 }, new int[3] { 1, 2, 5 } }; solveQueries(A, N, Q, query); }}// This code is contributed by Potta Lokesh |
Javascript
<script>// Javascript Program for the above approach// Function to calculate the Pairwise// Product Sum in range from L to Rfunction pairwiseProductSum(a, l, r) { let sum = 0; // Loop to iterate over all possible // pairs from L to R for (let j = l - 1; j <= r - 1; j++) { for (let k = j + 1; k <= r - 1; k++) { sum += a[j] * a[k]; } } // Print answer document.write(sum + "<br>");}// Function to update the Array// element at index P to Xfunction updateArray(a, p, x){ // Update the value at Pth // index in the array a[p - 1] = x;}// Function to solve Q queriesfunction solveQueries(a, n, Q, query) { for (let i = 0; i < Q; i++) { // If Query is of type 1 if (query[i][0] == 1) pairwiseProductSum(a, query[i][1], query[i][2]); // If Query is of type 2 else updateArray(a, query[i][1], query[i][2]); }}// Driver Codelet A = [5, 7, 2, 3, 1];let N = A.length;let Q = 3;let query = [ [1, 1, 3], [2, 2, 5], [1, 2, 5],];solveQueries(A, N, Q, query);// This code is contributed by gfgking.</script> |
Output:
59 41
Time Complexity: O(N2) for pairwise product sum query and O(1) for update query.
Space Complexity: O(N)
Efficient Approach: The complexity per query can be reduced to O(N) using the prefix sum technique discussed here.
Better Approach: A better approach to further reduce the complexity is using Fenwick Tree based on the following observations:
Given that
(a + b + c)2 = a2 + b2 + c2 + 2*(a*b + b*c + c*a)
Let required Pairwise Product Sum be P
Let E = (a1 + a2 + a3 + a4 … + an)2
=> E = a12 + a22 + … + an2 + 2*(a1*a2 + a1*a3 + ….)
=> E = a12 + a22 + … + an2 + 2*(P)
=> P = ( E – (a12 + a22 + …. + an2) ) / 2
So, P = (E – Q)/2 where Q = (a12 + a22 + …. + an2)
According to the above observation, we can maintain two Fenwick trees.
- First Fenwick tree will keep track of the sum of elements in the given range with update queries. This can be used to calculate E for any given range.
- Similarly, the second Fenwick tree will keep track of the sum of the square of elements in the given range with update queries. This can be used to calculate Q for any given range. Thereafter, P can be easily calculated as P = (E – Q)/2.
Below is the implementation of the above approach:
C++
<script>// javascript Program for the above approachvar MAXN = 100000;// Vector to store fenwick tree// of the 1st typevar bit1 = Array.from({length: MAXN}, (_, i) => 0);// Vector to store fenwick tree// of the 2nd typevar bit2 = Array.from({length: MAXN}, (_, i) => 0);// Function to update the value// at idx index in fenwick treefunction update(idx , val , bit){ while (idx < bit.length) { bit[idx] += val; idx += idx & (-idx); }}// Function to return the sum of values// stored from O to idx index in the// array using Fenwick Treefunction Query(idx , bit){ var res = 0; while (idx > 0) { res += bit[idx]; idx -= idx & (-idx); } return res;}// Function to build the Fenwick// tree from the a Arrayfunction buildFenwickTree(a , n){ for (var i = 1; i <= n; i++) { // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1], bit1); // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1] * a[i - 1], bit2); }}// Function to find the Pairwise// Product Sum in the range L to Rfunction pairwiseProductSum(a , l , r){ var sum, e, q; // Function call to calculate E // in the given range e = Query(r, bit1) - Query(l - 1, bit1); e = e * e; // Function call to calculate E // in the given range q = Query(r, bit2) - Query(l - 1, bit2); sum = (e - q) / 2; // Print Answer document.write(sum +"<br>");}// Function to update the Fenwick// tree and the array element at// index P to the new value Xfunction updateArray(a , p , x){ // Function call to update the // value in 1st Fenwick Tree update(p, -a[p - 1], bit1); update(p, x, bit1); // Function call to update the // value in 2nd Fenwick Tree update(p, -a[p - 1] * a[p - 1], bit2); update(p, x * x, bit2); a[p - 1] = x;}// Function to solve Q queriesfunction solveQueries( a , n, Q , query){ // Function Call to build the // Fenwick Tree buildFenwickTree(a, n); for (var i = 0; i < Q; i++) { // If Query is of type 1 if (query[i][0] == 1) pairwiseProductSum( a, query[i][1], query[i][2]); // If Query is of type 2 else updateArray( a, query[i][1], query[i][2]); }}// Driver Code var A = [ 5, 7, 2, 3, 1 ]; var N = A.length; var Q = 3; var query = [ [ 1, 1, 3 ], [ 2, 2, 5 ], [ 1, 2, 5 ] ]; solveQueries(A, N, Q, query);// This code is contributed by 29AjayKumar </script> |
Java
// Java Program for the above approachclass GFG{static final int MAXN = 100000;// Vector to store fenwick tree// of the 1st typestatic int []bit1 = new int[MAXN];// Vector to store fenwick tree// of the 2nd typestatic int []bit2 = new int[MAXN];// Function to update the value// at idx index in fenwick treestatic void update(int idx, int val, int []bit){ while (idx < bit.length) { bit[idx] += val; idx += idx & (-idx); }}// Function to return the sum of values// stored from O to idx index in the// array using Fenwick Treestatic int query(int idx, int []bit){ int res = 0; while (idx > 0) { res += bit[idx]; idx -= idx & (-idx); } return res;}// Function to build the Fenwick// tree from the a[] Arraystatic void buildFenwickTree(int a[], int n){ for (int i = 1; i <= n; i++) { // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1], bit1); // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1] * a[i - 1], bit2); }}// Function to find the Pairwise// Product Sum in the range L to Rstatic void pairwiseProductSum(int a[], int l, int r){ int sum, e, q; // Function call to calculate E // in the given range e = query(r, bit1) - query(l - 1, bit1); e = e * e; // Function call to calculate E // in the given range q = query(r, bit2) - query(l - 1, bit2); sum = (e - q) / 2; // Print Answer System.out.print(sum +"\n");}// Function to update the Fenwick// tree and the array element at// index P to the new value Xstatic void updateArray(int[] a, int p, int x){ // Function call to update the // value in 1st Fenwick Tree update(p, -a[p - 1], bit1); update(p, x, bit1); // Function call to update the // value in 2nd Fenwick Tree update(p, -a[p - 1] * a[p - 1], bit2); update(p, x * x, bit2); a[p - 1] = x;}// Function to solve Q queriesstatic void solveQueries( int[] a, int n, int Q, int query[][]){ // Function Call to build the // Fenwick Tree buildFenwickTree(a, n); for (int i = 0; i < Q; i++) { // If Query is of type 1 if (query[i][0] == 1) pairwiseProductSum( a, query[i][1], query[i][2]); // If Query is of type 2 else updateArray( a, query[i][1], query[i][2]); }}// Driver Codepublic 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);}}// This code is contributed by Princi Singh |
C#
// C# Program for the above approachusing System;class GFG { static int MAXN = 100000; // Vector to store fenwick tree // of the 1st type static int[] bit1 = new int[MAXN]; // Vector to store fenwick tree // of the 2nd type static int[] bit2 = new int[MAXN]; // Function to update the value // at idx index in fenwick tree static void update(int idx, int val, int[] bit) { while (idx < bit.Length) { bit[idx] += val; idx += idx & (-idx); } } // Function to return the sum of values // stored from O to idx index in the // array using Fenwick Tree static int query(int idx, int[] bit) { int res = 0; while (idx > 0) { res += bit[idx]; idx -= idx & (-idx); } return res; } // Function to build the Fenwick // tree from the a[] Array static void buildFenwickTree(int[] a, int n) { for (int i = 1; i <= n; i++) { // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1], bit1); // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1] * a[i - 1], bit2); } } // Function to find the Pairwise // Product Sum in the range L to R static void pairwiseProductSum(int[] a, int l, int r) { int sum, e, q; // Function call to calculate E // in the given range e = query(r, bit1) - query(l - 1, bit1); e = e * e; // Function call to calculate E // in the given range q = query(r, bit2) - query(l - 1, bit2); sum = (e - q) / 2; // Print Answer Console.WriteLine(sum); } // Function to update the Fenwick // tree and the array element at // index P to the new value X static void updateArray(int[] a, int p, int x) { // Function call to update the // value in 1st Fenwick Tree update(p, -a[p - 1], bit1); update(p, x, bit1); // Function call to update the // value in 2nd Fenwick Tree update(p, -a[p - 1] * a[p - 1], bit2); update(p, x * x, bit2); a[p - 1] = x; } // Function to solve Q queries static void solveQueries(int[] a, int n, int Q, int[, ] query) { // Function Call to build the // Fenwick Tree buildFenwickTree(a, n); for (int i = 0; i < Q; i++) { // If Query is of type 1 if (query[i, 0] == 1) pairwiseProductSum(a, query[i, 1], query[i, 2]); // If Query is of type 2 else updateArray(a, query[i, 1], query[i, 2]); } } // Driver Code 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); }}// This code is contributed by ukasp. |
Javascript
<script>// javascript Program for the above approachvar MAXN = 100000;// Vector to store fenwick tree// of the 1st typevar bit1 = Array.from({length: MAXN}, (_, i) => 0);// Vector to store fenwick tree// of the 2nd typevar bit2 = Array.from({length: MAXN}, (_, i) => 0);// Function to update the value// at idx index in fenwick treefunction update(idx , val , bit){ while (idx < bit.length) { bit[idx] += val; idx += idx & (-idx); }}// Function to return the sum of values// stored from O to idx index in the// array using Fenwick Treefunction Query(idx , bit){ var res = 0; while (idx > 0) { res += bit[idx]; idx -= idx & (-idx); } return res;}// Function to build the Fenwick// tree from the a Arrayfunction buildFenwickTree(a , n){ for (var i = 1; i <= n; i++) { // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1], bit1); // Function call to update // the ith element in the // first Fenwick Tree update(i, a[i - 1] * a[i - 1], bit2); }}// Function to find the Pairwise// Product Sum in the range L to Rfunction pairwiseProductSum(a , l , r){ var sum, e, q; // Function call to calculate E // in the given range e = Query(r, bit1) - Query(l - 1, bit1); e = e * e; // Function call to calculate E // in the given range q = Query(r, bit2) - Query(l - 1, bit2); sum = (e - q) / 2; // Print Answer document.write(sum );}// Function to update the Fenwick// tree and the array element at// index P to the new value Xfunction updateArray(a, p, x){ // Function call to update the // value in 1st Fenwick Tree update(p, -a[p - 1], bit1); update(p, x, bit1); // Function call to update the // value in 2nd Fenwick Tree update(p, -a[p - 1] * a[p - 1], bit2); update(p, x * x, bit2); a[p - 1] = x;}// Function to solve Q queriesfunction solveQueries( a , n, Q , query){ // Function Call to build the // Fenwick Tree buildFenwickTree(a, n); for (var i = 0; i < Q; i++) { // If Query is of type 1 if (query[i][0] == 1) pairwiseProductSum( a, query[i][1], query[i][2]); // If Query is of type 2 else updateArray( a, query[i][1], query[i][2]); }}// Driver Code var A = [ 5, 7, 2, 3, 1 ]; var N = A.length; var Q = 3; var query = [ [ 1, 1, 3 ], [ 2, 2, 5 ], [ 1, 2, 5 ] ]; solveQueries(A, N, Q, query);// This code is contributed by 29AjayKumar </script> |
Python3
# Python Program for the above approachMAXN = 100000;# Vector to store fenwick tree# of the 1st typebit1 = [0 for i in range(MAXN)];# Vector to store fenwick tree# of the 2nd typebit2 = [0 for i in range(MAXN)];# Function to update the value# at idx index in fenwick treedef update(idx, val, bit): while (idx < len(bit)): bit[idx] += val; idx += idx & (-idx);# Function to return the sum of values# stored from O to idx index in the# array using Fenwick Treedef querys(idx, bit): res = 0; while (idx > 0): res += bit[idx]; idx -= idx & (-idx); return res;# Function to build the Fenwick# tree from the a Arraydef buildFenwickTree(a, n): global bit1,bit2 for i in range(1,n+1): # Function call to update # the ith element in the # first Fenwick Tree update(i, a[i - 1], bit1); # Function call to update # the ith element in the # first Fenwick Tree update(i, a[i - 1] * a[i - 1], bit2);# Function to find the Pairwise# Product Sum in the range L to Rdef pairwiseProductSum(a, l, r): global bit1, bit2; sum, e, q=0,0,0; # Function call to calculate E # in the given range e = querys(r, bit1) - querys(l - 1, bit1); e = e * e; # Function call to calculate E # in the given range q = querys(r, bit2) - querys(l - 1, bit2); sum = (e - q) // 2; # Print Answer print(sum, " ");# Function to update the Fenwick# tree and the array element at# index P to the new value Xdef updateArray(a, p, x): global bit1,bit2 # Function call to update the # value in 1st Fenwick Tree update(p, -a[p - 1], bit1); update(p, x, bit1); # Function call to update the # value in 2nd Fenwick Tree update(p, -a[p - 1] * a[p - 1], bit2); update(p, x * x, bit2); a[p - 1] = x;# Function to solve Q queriesdef solveQueries(a, n, Q, query): # Function Call to build the # Fenwick Tree buildFenwickTree(a, n); for i in range(Q): # If Query is of type 1 if (query[i][0] == 1): pairwiseProductSum(a, query[i][1], query[i][2]); # If Query is of type 2 else: updateArray(a, query[i][1], query[i][2]);# Driver Codeif __name__ == '__main__': A = [5, 7, 2, 3, 1]; N = len(A); Q = 3; query = [[1, 1, 3], [2, 2, 5], [1, 2, 5]]; solveQueries(A, N, Q, query); # This code contributed by shikhasingrajput |
Output:
59 41
Time Complexity: O(N*log N) for the construction of Fenwick tree
O(log N) for the pairwise product sum query
O(log N) for the update query.
Auxiliary space: O(N)
