Consultas para multiplicar el subarreglo dado con el número dado X e imprimir la suma

Dada una array arr[] y consultas Q donde cada consulta contiene tres números enteros (l, r, x), la tarea es imprimir la suma de los elementos en el rango [l,r] después de multiplicar cada elemento con x.
 

Query(l, r, x) = 
   arr[l]*x + arr[l+1]*x + .... arr[r-1]*x + arr[r]*x

Nota : la multiplicación con x se realiza para calcular la respuesta y no se actualiza en la array de entrada en ningún paso de una consulta.
Ejemplos: 
 

Entrada: arr[] = {2, 3, 4, 2, 5, 1} 
Q[] = {{2, 4, 5}, {1, 1, 4}} 
Salida: 55 12 
Explicación:  
Consulta1: l = 2 r = 4 x = 5 
ans = arr[2]*5 + arr[3]*6 + ar[4]*7 
= 4*5 + 2*5 + 5*5 
= 55 
Consulta2: l = 1 r = 1 x = 4 
ans = arr[1]*4 
= 3*4 = 12
Entrada: arr[] = {2, 3, 4, 2} 
Q[] = {{1, 1, 8}} 
Salida: 16 
Explicación :  
Consulta1: l = 1 r = 1 x = 8 
ans = arr[1]*8 
= 2*8 = 16 
 

Enfoque ingenuo: la idea es iterar sobre cada consulta de la array y para cada consulta iterar sobre los elementos del rango [l, r] y encontrar la suma de cada elemento multiplicada por x. 
Complejidad de tiempo: O(Q*N)
Enfoque eficiente: la idea es precalcular la suma del prefijo de la array, luego para cada consulta encontrar la suma de los elementos del rango [l, r] y multiplicar por x para encontrar la respuesta de cada consulta. 
A continuación se muestran las fórmulas para calcular la respuesta de cada consulta: 
 

// pre_sum[i] denotes the prefix sum of
// the array from the array 0 to i
answer = x * (pre_sum[r] - pre_sum[l-1])

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to multiply
// the given subarray by the x
// for multiple queries of the Q
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to answer each query
int query(vector<int> pre_sum, int n,
         int l, int r, int val)
{
    int ans;
    int temp = 0;
    if (l > 0) {
        temp = pre_sum[l-1];
    }
    ans = val * (pre_sum[r] - temp);
    return ans;
}
 
// Function to multiply the subarray
// by the x for multiple Queries
void multiplyArray(int arr[],
 vector<pair<pair<int, int>, int>> q,
                             int n){
    vector<int> pre_sum;
    int s = 0;
     
    // Loop to compute the prefix
    // sum of the array
    for (int i = 0; i < n; i++){
        s += arr[i];
        pre_sum.push_back(s);
    }
     
    // Loop to answer each query
    for(auto i: q){
        cout << query(pre_sum, n, i.first.first,
         i.first.second, i.second) << endl;
    }
}
 
// Driver Code
int main()
{
    // Array
    int arr[] = { 2, 3, 4, 2, 5, 1 };
    int n = 6;
    vector<pair<pair<int, int>, int>> q;
    q.push_back({{2, 4}, 5});
    q.push_back({{1, 1}, 4});
    q.push_back({{1, 3}, -2});
     
    // Function Call
    multiplyArray(arr, q, n);
     
    return 0;
}

/*package whatever //do not write package name here */
// Java implementation to multiply
// the given subarray by the x
// for multiple queries of the Q
import java.io.*;
import java.util.ArrayList;
class GFG
{
 
  // Function to answer each query
  public static int query(ArrayList<Integer> pre_sum,
                          int n, int l, int r, int val)
  {
    int ans;
    int temp = 0;
    if (l > 0)
    {
      temp = pre_sum.get(l - 1);
    }
    ans = val * (pre_sum.get(r) - temp);
    return ans;
  }
 
  // Function to multiply the subarray
  // by the x for multiple Queries
  public static void multiplyArray(int arr[],
                                   ArrayList<pair> q,
                                   int n)
  {
    ArrayList<Integer> pre_sum = new ArrayList<>();
    int s = 0;
 
    // Loop to compute the prefix
    // sum of the array
    for (int i = 0; i < n; i++)
    {
      s += arr[i];
      pre_sum.add(s);
    }
 
    // Loop to answer each query
    for(int i = 0; i < q.size(); i++)
    {
      System.out.println(query(pre_sum, n,
                               q.get(i).pr.a,
                               q.get(i).pr.b,
                               q.get(i).second));
    }
  }
 
  // Driver Code
  public static void main(String [] args)
  {
    // Array
    int arr[] = { 2, 3, 4, 2, 5, 1 };
    int n = 6;
    ArrayList<pair> q = new ArrayList<>();
    q.add(new pair(new pair1(2, 4), 5));
    q.add(new pair(new pair1(1, 1), 4));
    q.add(new pair(new pair1(1, 3), -2));
 
    // Function Call
    multiplyArray(arr, q, n);
  }
}
class pair
{
 
  pair1 pr;
  int second;
 
  pair(pair1 pr, int second)
  {
    this.pr = pr;
    this.second = second;
  }
}
class pair1
{
  int a;
  int b;
  pair1(int a, int b)
  {
    this.a = a;
    this.b = b;
  }
}
 
// This code is contributed by aditya7409

# Python3 implementation to multiply
# the given subarray by the x
# for multiple queries of the Q
  
# Function to answer each query
def query(pre_sum, n, l, r, val):
 
    ans = 0
    temp = 0;
    if (l > 0):
        temp = pre_sum[l - 1];
     
    ans = val * (pre_sum[r] - temp);
    return ans;
   
# Function to multiply the subarray
# by the x for multiple Queries
def multiplyArray(arr, q, n):
     
    pre_sum = []
    s = 0;
      
    # Loop to compute the prefix
    # sum of the array
    for i in range(n):
 
        s += arr[i];
        pre_sum.append(s);
          
    # Loop to answer each query
    for i in q:
        print(query(pre_sum, n, i[0][0], i[0][1], i[1]))
         
# Driver Code
if __name__=='__main__':
 
    # Array
    arr = [ 2, 3, 4, 2, 5, 1 ]
    n = 6;
    q = []
    q.append([[2, 4], 5])
    q.append([[1, 1], 4])
    q.append([[1, 3], -2])
      
    # Function Call
    multiplyArray(arr, q, n);
      
# this code is contributed by rutvik_56

// C# implementation to multiply
// the given subarray by the x
// for multiple queries of the Q
using System;
using System.Collections.Generic;
class GFG
{
     
    // Function to answer each query
    static int query(List<int> pre_sum, int n,
             int l, int r, int val)
    {
        int ans;
        int temp = 0;
        if (l > 0)
        {
            temp = pre_sum[l - 1];
        }
        ans = val * (pre_sum[r] - temp);
        return ans;
    }
      
    // Function to multiply the subarray
    // by the x for multiple Queries
    static void multiplyArray(int[] arr, List<Tuple<Tuple<int, int>, int>> q, int n)
    {
        List<int> pre_sum = new List<int>();
        int s = 0;
          
        // Loop to compute the prefix
        // sum of the array
        for (int i = 0; i < n; i++)
        {
            s += arr[i];
            pre_sum.Add(s);
        }
          
        // Loop to answer each query
        foreach(Tuple<Tuple<int, int>, int> i in q)
        {
            Console.WriteLine(query(pre_sum, n, i.Item1.Item1,
                                    i.Item1.Item2, i.Item2));
        }
    }
 
  // Driver code
  static void Main()
  {
     
    // Array
    int[] arr = { 2, 3, 4, 2, 5, 1 };
    int n = 6;
    List<Tuple<Tuple<int, int>, int>> q = new List<Tuple<Tuple<int, int>, int>>();
    q.Add(new Tuple<Tuple<int, int>, int>(new Tuple<int, int>(2,4), 5));
    q.Add(new Tuple<Tuple<int, int>, int>(new Tuple<int, int>(1,1), 4));
    q.Add(new Tuple<Tuple<int, int>, int>(new Tuple<int, int>(1,3), -2));
      
    // Function Call
    multiplyArray(arr, q, n);
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// Javascript implementation to multiply
// the given subarray by the x
// for multiple queries of the Q
 
// Function to answer each query
function query(pre_sum, n, l, r, val)
{
    var ans;
    var temp = 0;
    if (l > 0) {
        temp = pre_sum[l-1];
    }
    ans = val * (pre_sum[r] - temp);
    return ans;
}
 
// Function to multiply the subarray
// by the x for multiple Queries
function multiplyArray(arr, q, n){
    var pre_sum = [];
    var s = 0;
     
    // Loop to compute the prefix
    // sum of the array
    for (var i = 0; i < n; i++){
        s += arr[i];
        pre_sum.push(s);
    }
     
    // Loop to answer each query
    q.forEach(i => {
        document.write( query(pre_sum, n, i[0][0],
         i[0][1], i[1]) + "<br>");
    });
}
 
// Driver Code
// Array
var arr = [2, 3, 4, 2, 5, 1];
var n = 6;
var q = [];
q.push([[2, 4], 5]);
q.push([[1, 1], 4]);
q.push([[1, 3], -2]);
 
// Function Call
multiplyArray(arr, q, n);
 
// This code is contributed by rrrtnx.
</script>

55
12
-18

Complejidad temporal:  O(Q + N) 
Espacio auxiliar: O(N)