Consultas de rango para sumar y restar alternativamente en una array dada

Dada una array arr[] de N enteros y Q consultas donde cada fila consta de dos números L y R que denotan el rango [L, R] , la tarea es encontrar el valor de la suma y resta alternativas del elemento de la array entre el rango [izquierda, derecha] .

Ejemplos: 

Entrada: arr[] = {10, 13, 15, 2, 45, 31, 22, 3, 27}, Q[][] = {{2, 5}, {6, 8}, {1, 7} , {4, 8}, {0, 5}} 
Salida: 27 46 -33 60 24 
Explicación: 
El resultado de la consulta {2, 5} es 27 (15 – 2 + 45 – 31) 
Resultado de la consulta {6, 8} es 46 ( 22 – 3 + 27) 
El resultado de la consulta {1, 7} es -33 ( 13 – 15 + 2 – 45 + 31 – 22 + 3) 
El resultado de la consulta {4, 8} es 60 ( 45 – 31 + 22 – 3 + 27) 
El resultado de la consulta {0, 5} es 24 (10 – 13 + 15 – 2 + 45 – 31)

Entrada: arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1}, Q[] = {{2, 5}, {6, 8}, {1, 7}, { 4, 8}, {0, 5}} 
Salida: 0 1 1 1 0 

Enfoque ingenuo: la idea ingenua es iterar desde el índice L a R para cada consulta y encontrar el valor de sumar y restar alternativamente los elementos de la array e imprimir el valor después de realizar las operaciones.

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;
 
// Structure to represent a range query
struct Query {
    int L, R;
};
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
int findResultUtil(int arr[],
                   int L, int R)
{
    int result = 0;
 
    // A boolean variable flag to
    // alternatively add and subtract
    bool flag = false;
 
    // Iterate from [L, R]
    for (int i = L; i <= R; i++) {
 
        // if flag is false, then
        // add & toggle the flag
        if (flag == false) {
            result = result + arr[i];
            flag = true;
        }
 
        // if flag is true subtract
        // and toggle the flag
        else {
            result = result - arr[i];
            flag = false;
        }
    }
 
    // Return the final result
    return result;
}
 
// Function to find the value
// for each query
void findResult(int arr[], int n,
                Query q[], int m)
{
 
    // Iterate for each query
    for (int i = 0; i < m; i++) {
        cout << findResultUtil(arr,
                               q[i].L,
                               q[i].R)
             << " ";
    }
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 10, 13, 15, 2, 45,
                  31, 22, 3, 27 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Given Queries
    Query q[] = { { 2, 5 }, { 6, 8 },
                  { 1, 7 }, { 4, 8 },
                  { 0, 5 } };
 
    int m = sizeof(q) / sizeof(q[0]);
 
    // Function Call
    findResult(arr, n, q, m);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Structure to represent a range query
static class Query
{
    int L, R;
    public Query(int l, int r)
    {
        super();
        L = l;
        R = r;
    }
};
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
static int findResultUtil(int arr[],
                          int L, int R)
{
    int result = 0;
 
    // A boolean variable flag to
    // alternatively add and subtract
    boolean flag = false;
 
    // Iterate from [L, R]
    for(int i = L; i <= R; i++)
    {
         
        // If flag is false, then
        // add & toggle the flag
        if (flag == false)
        {
            result = result + arr[i];
            flag = true;
        }
 
        // If flag is true subtract
        // and toggle the flag
        else
        {
            result = result - arr[i];
            flag = false;
        }
    }
 
    // Return the final result
    return result;
}
 
// Function to find the value
// for each query
static void findResult(int arr[], int n,
                       Query q[], int m)
{
 
    // Iterate for each query
    for(int i = 0; i < m; i++)
    {
        System.out.print(findResultUtil(arr,
              q[i].L, q[i].R) + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given array
    int arr[] = { 10, 13, 15, 2, 45,
                  31, 22, 3, 27 };
 
    int n = arr.length;
 
    // Given Queries
    Query q[] = { new Query(2, 5), new Query(6, 8),
                  new Query(1, 7), new Query(4, 8),
                  new Query(0, 5) };
 
    int m = q.length;
 
    // Function call
    findResult(arr, n, q, m);
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for the above approach
 
# Function to find the result of
# alternatively adding and subtracting
# elements in the range [L, R]
def findResultUtil(arr, L, R):
     
    result = 0
 
    # A boolean variable flag to
    # alternatively add and subtract
    flag = False
 
    # Iterate from [L, R]
    for i in range(L, R + 1):
         
        # If flag is False, then
        # add & toggle the flag
        if (flag == False):
            result = result + arr[i]
            flag = True
 
        # If flag is True subtract
        # and toggle the flag
        else:
            result = result - arr[i]
            flag = False
 
    # Return the final result
    return result
 
# Function to find the value
# for each query
def findResult(arr, n, q, m):
 
    # Iterate for each query
    for i in range(m):
        print(findResultUtil(arr,
                             q[i][0],
                             q[i][1]),
                             end = " ")
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    arr = [ 10, 13, 15, 2, 45,
            31, 22, 3, 27 ]
 
    n = len(arr)
 
    # Given Queries
    q = [ [ 2, 5 ], [ 6, 8 ],
          [ 1, 7 ], [ 4, 8 ],
          [ 0, 5 ] ]
 
    m = len(q)
 
    # Function Call
    findResult(arr, n, q, m)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
class GFG{
 
// Structure to represent a range query
class Query
{
    public int L, R;
    public Query(int l, int r)
    {
        L = l;
        R = r;
    }
};
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
static int findResultUtil(int []arr,
                          int L, int R)
{
    int result = 0;
 
    // A bool variable flag to
    // alternatively add and subtract
    bool flag = false;
 
    // Iterate from [L, R]
    for(int i = L; i <= R; i++)
    {
         
        // If flag is false, then
        // add & toggle the flag
        if (flag == false)
        {
            result = result + arr[i];
            flag = true;
        }
 
        // If flag is true subtract
        // and toggle the flag
        else
        {
            result = result - arr[i];
            flag = false;
        }
    }
 
    // Return the readonly result
    return result;
}
 
// Function to find the value
// for each query
static void findResult(int []arr, int n,
                       Query []q, int m)
{
 
    // Iterate for each query
    for(int i = 0; i < m; i++)
    {
        Console.Write(findResultUtil(arr,
              q[i].L, q[i].R) + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
 
    // Given array
    int []arr = { 10, 13, 15, 2, 45,
                  31, 22, 3, 27 };
 
    int n = arr.Length;
 
    // Given Queries
    Query []q = { new Query(2, 5), new Query(6, 8),
                  new Query(1, 7), new Query(4, 8),
                  new Query(0, 5) };
 
    int m = q.Length;
 
    // Function call
    findResult(arr, n, q, m);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L, R]
function findResultUtil(arr, L, R)
{
    var result = 0;
 
    // A boolean variable flag to
    // alternatively add and subtract
    var flag = false;
 
    // Iterate from [L, R]
    for (var i = L; i <= R; i++) {
 
        // if flag is false, then
        // add & toggle the flag
        if (flag == false) {
            result = result + arr[i];
            flag = true;
        }
 
        // if flag is true subtract
        // and toggle the flag
        else {
            result = result - arr[i];
            flag = false;
        }
    }
 
    // Return the final result
    return result;
}
 
// Function to find the value
// for each query
function findResult(arr, n, q, m)
{
 
    // Iterate for each query
    for (var i = 0; i < m; i++) {
        document.write( findResultUtil(arr,
                               q[i][0],
                               q[i][1])
             + " ");
    }
}
 
// Driver Code
// Given array
var arr = [10, 13, 15, 2, 45,
              31, 22, 3, 27 ];
var n = arr.length;
// Given Queries
var q = [ [ 2, 5 ], [ 6, 8 ],
              [ 1, 7 ], [ 4, 8 ],
              [ 0, 5 ] ];
var m = q.length;
// Function Call
findResult(arr, n, q, m);
 
 
</script>
Producción:

27 46 -33 60 24

 

Complejidad temporal: O(N*Q)  
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque eficiente es usar Prefix Sum Array para resolver el problema anterior. A continuación se muestran los pasos: 

  1. Inicialice el primer elemento de la array de prefijos (por ejemplo , pre[] ) en el primer elemento de arr[] .
  2. Recorra un índice de 1 a N-1 y sume y reste alternativamente los elementos de arr[i] de pre[i-1] y guárdelo en pre[i] para hacer una array de prefijos.
  3. Ahora, itere a través de cada consulta de 1 a Q y encuentre el resultado sobre la base de los siguientes casos: 
    • Caso 1: si L es cero, el resultado es pre[R] .
    • Caso 2: si L no es cero, encuentre el resultado usando la ecuación:
result = Query(L, R) = pre[R] – pre[L - 1]
  • Si L es impar, multiplique el resultado anterior por -1 .

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;
 
// Structure to represent a query
struct Query {
    int L, R;
};
 
// This function fills the Prefix Array
void fillPrefixArray(int arr[], int n,
                    int prefixArray[])
{
    // Initialise the prefix array
    prefixArray[0] = arr[0];
 
    // Iterate all the element of arr[]
    // and update the prefix array
    for (int i = 1; i < n; i++) {
 
        // If n is even then, add the
        // previous value of prefix array
        // with the current value of arr
        if (i % 2 == 0) {
 
            prefixArray[i]
                = prefixArray[i - 1]
                + arr[i];
        }
 
        // if n is odd, then subtract
        // the previous value of prefix
        // Array from current value
        else {
            prefixArray[i]
                = prefixArray[i - 1]
                - arr[i];
        }
    }
}
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
int findResultUtil(int prefixArray[],
                int L, int R)
{
    int result;
 
    // Case 1 : when L is zero
    if (L == 0) {
        result = prefixArray[R];
    }
 
    // Case 2 : When L is non zero
    else {
        result = prefixArray[R]
                - prefixArray[L - 1];
    }
 
    // If L is odd means range starts from
    // odd position multiply result by -1
    if (L & 1) {
        result = result * (-1);
    }
 
    // Return the final result
    return result;
}
 
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
void findResult(int arr[], int n,
                Query q[], int m)
{
 
    // Declare prefix array
    int prefixArray[n];
 
    // Function Call to fill prefix arr[]
    fillPrefixArray(arr, n, prefixArray);
 
    // Iterate for each query
    for (int i = 0; i < m; i++) {
 
        cout << findResultUtil(prefixArray,
                            q[i].L,
                            q[i].R)
            << " ";
    }
}
 
// Driver Code
int main()
{
 
    // Given array
    int arr[] = { 10, 13, 15, 2, 45,
                31, 22, 3, 27 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Given Queries
    Query q[] = { { 2, 5 }, { 6, 8 },
                { 1, 7 }, { 4, 8 },
                { 0, 5 } };
 
    int m = sizeof(q) / sizeof(q[0]);
 
    // Function Call
    findResult(arr, n, q, m);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Structure to represent a query
static class Query
{
    int L, R;
 
    public Query(int l, int r)
    {
        super();
        L = l;
        R = r;
    }
};
 
// This function fills the Prefix Array
static void fillPrefixArray(int arr[], int n,
                            int prefixArray[])
{
    // Initialise the prefix array
    prefixArray[0] = arr[0];
 
    // Iterate all the element of arr[]
    // and update the prefix array
    for (int i = 1; i < n; i++)
    {
 
        // If n is even then, add the
        // previous value of prefix array
        // with the current value of arr
        if (i % 2 == 0)
        {
            prefixArray[i] = prefixArray[i - 1] +
                                           arr[i];
        }
 
        // if n is odd, then subtract
        // the previous value of prefix
        // Array from current value
        else
        {
            prefixArray[i] = prefixArray[i - 1] -
                                           arr[i];
        }
    }
}
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
static int findResultUtil(int prefixArray[],
                          int L, int R)
{
    int result;
 
    // Case 1 : when L is zero
    if (L == 0)
    {
        result = prefixArray[R];
    }
 
    // Case 2 : When L is non zero
    else
    {
        result = prefixArray[R] -
                   prefixArray[L - 1];
    }
 
    // If L is odd means range starts from
    // odd position multiply result by -1
    if (L % 2 == 1)
    {
        result = result * (-1);
    }
 
    // Return the final result
    return result;
}
 
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
static void findResult(int arr[], int n,
                         Query q[], int m)
{
 
    // Declare prefix array
    int []prefixArray = new int[n];
 
    // Function Call to fill prefix arr[]
    fillPrefixArray(arr, n, prefixArray);
 
    // Iterate for each query
    for (int i = 0; i < m; i++)
    {
        System.out.print(findResultUtil(
                           prefixArray, q[i].L,
                                        q[i].R) + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given array
    int arr[] = { 10, 13, 15, 2, 45,
                31, 22, 3, 27 };
 
    int n = arr.length;
 
    // Given Queries
    Query q[] = {new Query( 2, 5 ), new Query( 6, 8 ),
                 new Query( 1, 7 ), new Query( 4, 8 ),
                 new Query( 0, 5 )};
 
    int m = q.length;
 
    // Function Call
    findResult(arr, n, q, m);
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python program for the above approach
 
# Structure to represent a query
class Query:
    def __init__(self,l,r):
        self.L = l
        self.R = r
 
# This function fills the Prefix Array
def fillPrefixArray(arr, n, prefixArray):
     
    # Initialise the prefix array
    prefixArray[0] = arr[0]
 
    # Iterate all the element of arr[]
    # and update the prefix array
    for i in range(1,n):
         
        # If n is even then, add the
        # previous value of prefix array
        # with the current value of arr
        if (i % 2 == 0):
            prefixArray[i] = prefixArray[i - 1] + arr[i]
 
        # if n is odd, then subtract
        # the previous value of prefix
        # Array from current value
        else:
            prefixArray[i] = prefixArray[i - 1] - arr[i]
 
# Function to find the result of
# alternatively adding and subtracting
# elements in the range [L< R]
def findResultUtil(prefixArray, L, R):
 
    # Case 1 : when L is zero
    if (L == 0):
        result = prefixArray[R]
 
    # Case 2 : When L is non zero
    else:
        result = prefixArray[R] - prefixArray[L - 1]
 
    # If L is odd means range starts from
    # odd position multiply result by -1
    if (L % 2 == 1):
        result = result * (-1)
 
    # Return the final result
    return result
 
# Function to find the sum of all
# alternative add and subtract
# between ranges [L, R]
def findResult(arr, n, q, m):
     
    # Declare prefix array
    prefixArray = [0 for i in range(n)]
 
    # Function Call to fill prefix arr[]
    fillPrefixArray(arr, n, prefixArray)
     
    # Iterate for each query
    for i in range(m):
        print(findResultUtil(prefixArray, q[i].L,q[i].R),end = " ")
 
# Driver Code
 
# Given array
arr = [ 10, 13, 15, 2, 45, 31, 22, 3, 27 ]
n = len(arr)
 
# Given Queries
q = [ Query(2, 5), Query(6, 8), Query(1, 7), Query(4, 8), Query(0, 5)]
m = len(q)
 
# Function Call
findResult(arr, n, q, m)
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using System;
class GFG{
 
// Structure to represent a query
class Query
{
   public  int L, R;
 
    public Query(int l, int r)
    {
        L = l;
        R = r;
    }
};
 
// This function fills the Prefix Array
static void fillPrefixArray(int []arr, int n,
                            int []prefixArray)
{
    // Initialise the prefix array
    prefixArray[0] = arr[0];
 
    // Iterate all the element of []arr
    // and update the prefix array
    for (int i = 1; i < n; i++)
    {
 
        // If n is even then, add the
        // previous value of prefix array
        // with the current value of arr
        if (i % 2 == 0)
        {
            prefixArray[i] = prefixArray[i - 1] +
                                         arr[i];
        }
 
        // if n is odd, then subtract
        // the previous value of prefix
        // Array from current value
        else
        {
            prefixArray[i] = prefixArray[i - 1] -
                                         arr[i];
        }
    }
}
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
static int findResultUtil(int []prefixArray,
                          int L, int R)
{
    int result;
 
    // Case 1 : when L is zero
    if (L == 0)
    {
        result = prefixArray[R];
    }
 
    // Case 2 : When L is non zero
    else
    {
        result = prefixArray[R] -
                 prefixArray[L - 1];
    }
 
    // If L is odd means range starts from
    // odd position multiply result by -1
    if (L % 2 == 1)
    {
        result = result * (-1);
    }
 
    // Return the readonly result
    return result;
}
 
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
static void findResult(int []arr, int n,
                       Query []q, int m)
{
 
    // Declare prefix array
    int []prefixArray = new int[n];
 
    // Function Call to fill prefix []arr
    fillPrefixArray(arr, n, prefixArray);
 
    // Iterate for each query
    for (int i = 0; i < m; i++)
    {
        Console.Write(findResultUtil(
                           prefixArray, q[i].L,
                                        q[i].R) + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
 
    // Given array
    int []arr = { 10, 13, 15, 2, 45,
                31, 22, 3, 27 };
 
    int n = arr.Length;
 
    // Given Queries
    Query []q = {new Query( 2, 5 ), new Query( 6, 8 ),
                 new Query( 1, 7 ), new Query( 4, 8 ),
                 new Query( 0, 5 )};
 
    int m = q.Length;
 
    // Function Call
    findResult(arr, n, q, m);
}
}
 
// This code is contributed by Rohit_ranjan

Javascript

<script>
 
// Javascript program for the above approach
 
// Structure to represent a query
class Query
{
    constructor(l, r)
    {
        this.L = l;
        this.R = r;
    }
}
 
// This function fills the Prefix Array
function fillPrefixArray(arr, n, prefixArray)
{
     
    // Initialise the prefix array
    prefixArray[0] = arr[0];
  
    // Iterate all the element of arr[]
    // and update the prefix array
    for(let i = 1; i < n; i++)
    {
         
        // If n is even then, add the
        // previous value of prefix array
        // with the current value of arr
        if (i % 2 == 0)
        {
            prefixArray[i] = prefixArray[i - 1] +
                                           arr[i];
        }
  
        // if n is odd, then subtract
        // the previous value of prefix
        // Array from current value
        else
        {
            prefixArray[i] = prefixArray[i - 1] -
                                     arr[i];
        }
    }
}
 
// Function to find the result of
// alternatively adding and subtracting
// elements in the range [L< R]
function findResultUtil(prefixArray, L, R)
{
     let result;
  
    // Case 1 : when L is zero
    if (L == 0)
    {
        result = prefixArray[R];
    }
  
    // Case 2 : When L is non zero
    else
    {
        result = prefixArray[R] -
                 prefixArray[L - 1];
    }
  
    // If L is odd means range starts from
    // odd position multiply result by -1
    if (L % 2 == 1)
    {
        result = result * (-1);
    }
  
    // Return the final result
    return result;
}
 
// Function to find the sum of all
// alternative add and subtract
// between ranges [L, R]
function findResult(arr, n, q, m)
{
     
    // Declare prefix array
    let prefixArray = new Array(n);
  
    // Function Call to fill prefix arr[]
    fillPrefixArray(arr, n, prefixArray);
  
    // Iterate for each query
    for(let i = 0; i < m; i++)
    {
        document.write(findResultUtil(
                        prefixArray, q[i].L,
                                     q[i].R) + " ");
    }
}
 
// Driver Code
 
// Given array
let arr = [ 10, 13, 15, 2, 45,
            31, 22, 3, 27 ];
let n = arr.length;
 
// Given Queries
let q = [ new Query(2, 5), new Query(6, 8),
          new Query(1, 7), new Query(4, 8),
          new Query(0, 5)];
let m = q.length;
 
// Function Call
findResult(arr, n, q, m);
 
// This code is contributed by unknown2108
 
</script>

Producción:  

27 46 -33 60 24

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

Publicación traducida automáticamente

Artículo escrito por rahulrai27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *