Dada una array A[] que consta de N números enteros y Q consultas de los siguientes tipos, la tarea es imprimir el resultado de todas las consultas de actualización.
- (1, L, R): el primer tipo de consulta para encontrar la suma del producto de todos los pares desordenados del índice L a R en la array donde 1 <= L <= R <= N .
- (2, P, X): el segundo tipo de consulta para cambiar el valor del P -ésimo entero de la array a un nuevo valor X.
Ejemplo:
Entrada: A[] = {5 7 2 3 1}, Q = 3, Consultas[] = [[1, 1, 3], [2, 2, 5], [1, 2, 5]]
Salida:
59
41
Explicación:
Consulta 1: En la 1ra consulta, los pares posibles en el rango dado son (5, 7), (5, 2) y (7, 2). Entonces, la suma del producto por pares será (5*7) + (5*2) + (7*2) = 35 + 10 + 14 = 59.
Consulta 2: en la segunda consulta, actualice el segundo entero a 5, lo que hace la array como [5, 5, 2, 3, 1].
Consulta 3: en la tercera consulta, los pares posibles en el rango [2, 5] son (5, 2), (5, 3), (5, 1), (2, 3), (2, 1) y (3, 1). La suma del producto de estos pares es 41.Entrada: A[] = {7 3 2 1 4 5 8}, Q = 5, Consultas[] = [ [1, 1, 6], [2, 2, 4], [1, 2, 5], [ 2, 3, 8], [1, 4, 7]]
Salida: 59
41
6
Enfoque ingenuo: la forma sencilla de resolver esto es para el primer tipo de consulta, generar todos los pares desordenados en el rango de consulta dado e imprimir la suma del producto de estos pares. Para el segundo tipo de consultas, actualice el elemento de array según el valor dado.
A continuación se muestra la implementación del enfoque anterior:
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 R
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
cout << sum << endl;
}
// Function to update the Array
// element at index P to X
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 queries
void 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 Code
int 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 approach
import java.util.*;
class GFG{
// Function to calculate the Pairwise
// Product Sum in range from L to R
static 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 X
static 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 queries
static 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
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 29AjayKumar
Python3
# Python 3 Program for the above approach # Function to calculate the Pairwise # Product Sum in range from L to R def 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 X def updateArray(a, p, x): # Update the value at Pth # index in the array a[p - 1] = x # Function to solve Q queries def 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 Code if __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 approach
using System;
public class GFG{
// Function to calculate the Pairwise
// Product Sum in range from L to R
static 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 X
static 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 queries
static 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 R
function 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 X
function updateArray(a, p, x)
{
// Update the value at Pth
// index in the array
a[p - 1] = x;
}
// Function to solve Q queries
function 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 Code
let 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>
Producción:
59 41
Complejidad de tiempo: O(N 2 ) para consulta de suma de productos por pares y O(1) para consulta de actualización.
Complejidad espacial: O(N)
Enfoque eficiente: la complejidad por consulta se puede reducir a O(N) utilizando la técnica de suma de prefijos que se analiza aquí .
Mejor enfoque: un mejor enfoque para reducir aún más la complejidad es usar Fenwick Tree según las siguientes observaciones:
Dado que
(a + b + c) 2 = a 2 + b 2 + c 2 + 2*(a*b + b*c + c*a)
Sea P la suma requerida del producto por pares
Sea E = (a1 + a2 + a3 + a4 … + an) 2
=> E = a1 2 + a2 2 + … + an 2 + 2*(a1*a2 + a1*a3 + ….)
=> E = a1 2 + a2 2 + … + an 2 + 2*(P)
=> P = ( E – (a1 2 + a2 2 + …. + an 2 ) ) / 2
Entonces, P = (E – Q)/2 donde Q = (a1 2 + a2 2 +….+ un 2 )
De acuerdo con la observación anterior, podemos mantener dos árboles Fenwick.
- El primer árbol de Fenwick realizará un seguimiento de la suma de elementos en el rango dado con consultas de actualización . Esto se puede usar para calcular E para cualquier rango dado.
- De manera similar, el segundo árbol de Fenwick realizará un seguimiento de la suma del cuadrado de los elementos en el rango dado con consultas de actualización. Esto se puede usar para calcular Q para cualquier rango dado. A partir de entonces, P se puede calcular fácilmente como P = (E – Q)/2 .
A continuación se muestra la implementación del enfoque anterior:
C++
<script>
// javascript Program for the above approach
var MAXN = 100000;
// Vector to store fenwick tree
// of the 1st type
var bit1 = Array.from({length: MAXN}, (_, i) => 0);
// Vector to store fenwick tree
// of the 2nd type
var bit2 = Array.from({length: MAXN}, (_, i) => 0);
// Function to update the value
// at idx index in fenwick tree
function 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 Tree
function 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 Array
function 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 R
function 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 X
function 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 queries
function 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 approach
class GFG{
static final 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
System.out.print(sum +"\n");
}
// 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 Princi Singh
C#
// C# Program for the above approach
using 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 approach
var MAXN = 100000;
// Vector to store fenwick tree
// of the 1st type
var bit1 = Array.from({length: MAXN}, (_, i) => 0);
// Vector to store fenwick tree
// of the 2nd type
var bit2 = Array.from({length: MAXN}, (_, i) => 0);
// Function to update the value
// at idx index in fenwick tree
function 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 Tree
function 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 Array
function 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 R
function 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 X
function 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 queries
function 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 approach MAXN = 100000; # Vector to store fenwick tree # of the 1st type bit1 = [0 for i in range(MAXN)]; # Vector to store fenwick tree # of the 2nd type bit2 = [0 for i in range(MAXN)]; # Function to update the value # at idx index in fenwick tree def 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 Tree def 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 Array def 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 R def 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 X def 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 queries def 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 Code if __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
Producción:
59 41
Complejidad de tiempo: O(N*log N) para la construcción del árbol de Fenwick
O(log N) para la consulta de suma de productos por pares
O(log N) para la consulta de actualización.
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikeyasri23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA