Dos consultas de rango de segmentos de igual suma

Dada una array arr[] que consiste en N enteros positivos y algunas consultas que consisten en un rango [L, R] , la tarea es encontrar si la sub-array del rango de índice dado se puede dividir en dos partes contiguas de no- longitud cero y suma igual.
Ejemplos: 
 

Entrada: arr[] = {1, 1, 2, 3}, q[] = {{0, 1}, {1, 3}, {1, 2}} 
Salida: 
Sí 
Sí 
No 
q[0]: El la subarray se puede dividir en {1}, {1}. 
q[1]: el subconjunto se puede dividir en {1, 2}, {3}. 
q[2]: el subarreglo no se puede dividir en dos segmentos iguales.
Entrada: arr[] = {2, 1, 3, 4, 1, 2}, q[] = {{0, 5}, {1, 3}} 
Salida: 
No 
Sí 
 

Una solución simple será recorrer todo el rango y calcular la suma del rango. Luego, iteraremos a través de toda la array nuevamente. Vamos a resumir los elementos a partir del índice ‘L’. Si en cualquier paso encontramos que la suma actual es la mitad de la suma total del rango, el subconjunto representado por el rango se puede dividir en dos mitades iguales. Puede llevar hasta O(n) tiempo responder una consulta usando este enfoque.
Una mejor solución es usar una array de suma de prefijos. Primero, creamos una array de suma de prefijos p_arr de arr. Ahora, usando ‘p_arr’, podemos determinar la suma de todos los elementos en el rango ‘L’ a ‘R’ en tiempo O(1). Una vez que tenemos nuestra suma, necesitamos determinar si existe un índice ‘i’ deL a R-1 tal que la suma de todos los números entre L a i de la array original es la mitad de la suma del rango. Para eso, podemos simplemente insertar todos los valores en la array de suma de prefijos ‘p_arr’ en un mapa desordenado. 
 

Si el valor de sum es par y p_arr[l-1] + sum/2 existe en el mapa, la array se puede dividir en dos segmentos de igual suma. 
 

Por lo tanto, la complejidad del tiempo para responder una consulta se convierte en O(1).
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required prefix sum
void prefixSum(int* p_arr, int* arr, int n)
{
    p_arr[0] = arr[0];
    for (int i = 1; i < n; i++)
        p_arr[i] = arr[i] + p_arr[i - 1];
}
 
// Function to hash all the values of prefix
// sum array in an unordered map
void hashPrefixSum(int* p_arr, int n, unordered_set<int>& q)
{
    for (int i = 0; i < n; i++)
        q.insert(p_arr[i]);
}
 
// Function to check if a range
// can be divided into two equal parts
void canDivide(int* p_arr, int n,
               unordered_set<int>& q, int l, int r)
{
    // To store the value of sum
    // of entire range
    int sum;
 
    if (l == 0)
        sum = p_arr[r];
    else
        sum = p_arr[r] - p_arr[l - 1];
 
    // If value of sum is odd
    if (sum % 2 == 1) {
        cout << "No" << endl;
        return;
    }
 
    // To store p_arr[l-1]
    int beg = 0;
 
    if (l != 0)
        beg = p_arr[l - 1];
 
    // If the value exists in the map
    if (q.find(beg + sum / 2) != q.end())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 1, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // prefix-sum array
    int p_arr[n];
 
    prefixSum(p_arr, arr, n);
 
    // Map to store the values of prefix-sum
    unordered_set<int> q;
 
    hashPrefixSum(p_arr, n, q);
 
    // Perform queries
    canDivide(p_arr, n, q, 0, 1);
    canDivide(p_arr, n, q, 1, 3);
    canDivide(p_arr, n, q, 1, 2);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
class GFG {
 
// Function to find the required prefix sum
static void prefixSum(int[] p_arr, int[] arr, int n)
{
    p_arr[0] = arr[0];
    for (int i = 1; i < n; i++)
        p_arr[i] = arr[i] + p_arr[i - 1];
}
  
// Function to q all the values of prefix
// sum array in an unordered map
static void qPrefixSum(int[]p_arr, int n, HashSet<Integer>q)
{
    for (int i = 0; i < n; i++)
        q.add(p_arr[i]);
}
  
// Function to check if a range
// can be divided into two equal parts
static void canDivide(int[] p_arr, int n,
               HashSet<Integer>q, int l, int r)
{
    // To store the value of sum
    // of entire range
    int sum;
  
    if (l == 0)
        sum = p_arr[r];
    else
        sum = p_arr[r] - p_arr[l - 1];
  
    // If value of sum is odd
    if (sum % 2 == 1) {
        System.out.println("No");
        return;
    }
  
    // To store p_arr[l-1]
    int beg = 0;
  
    if (l != 0)
        beg = p_arr[l - 1];
  
    // If the value exists in the map
    if(q.contains(beg + sum / 2) && (beg + sum / 2)!=(int)q.toArray()[ q.size()-1 ] )
        System.out.println("Yes");
    else
        System.out.println("No");
}
  
// Driver code
 public static void main(String[] args) {
   int arr[] = { 1, 1, 2, 3 };
    int n = arr.length;
  
    // prefix-sum array
    int p_arr[] = new int[n];
  
    prefixSum(p_arr, arr, n);
  
    // Map to store the values of prefix-sum
    HashSet<Integer> q = new HashSet<>();
  
    qPrefixSum(p_arr, n, q);
  
    // Perform queries
    canDivide(p_arr, n, q, 0, 1);
    canDivide(p_arr, n, q, 1, 3);
    canDivide(p_arr, n, q, 1, 2);
    }
}
 
// This code contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to find the required prefix Sum
def prefixSum(p_arr, arr, n):
 
    p_arr[0] = arr[0]
    for i in range(1, n):
        p_arr[i] = arr[i] + p_arr[i - 1]
 
# Function to hash all the values of
# prefix Sum array in an unordered map
def hashPrefixSum(p_arr, n, q):
 
    for i in range(n):
        q[p_arr[i]] = 1
 
# Function to check if a range
# can be divided into two equal parts
def canDivide(p_arr, n, q, l, r):
     
    # To store the value of Sum
    # of entire range
    Sum = 0
 
    if (l == 0):
        Sum = p_arr[r]
    else:
        Sum = p_arr[r] - p_arr[l - 1]
 
    # If value of Sum is odd
    if (Sum % 2 == 1):
        print("No")
        return
     
    # To store p_arr[l-1]
    beg = 0
 
    if (l != 0):
        beg = p_arr[l - 1]
 
    # If the value exists in the map
    if (beg + Sum // 2 in q.keys()):
        print("Yes")
    else:
        print("No")
 
# Driver code
arr = [1, 1, 2, 3]
n = len(arr)
 
# prefix-Sum array
p_arr = [0 for i in range(n)]
 
prefixSum(p_arr, arr, n)
 
# Map to store the values
# of prefix-Sum
q = dict()
 
hashPrefixSum(p_arr, n, q)
 
# Perform queries
canDivide(p_arr, n, q, 0, 1)
canDivide(p_arr, n, q, 1, 3)
canDivide(p_arr, n, q, 1, 2)
 
# This code is contributed
# by mohit kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find the required prefix sum
static void prefixSum(int[] p_arr, int[] arr, int n)
{
    p_arr[0] = arr[0];
    for (int i = 1; i < n; i++)
        p_arr[i] = arr[i] + p_arr[i - 1];
}
 
// Function to q all the values of prefix
// sum array in an unordered map
static void qPrefixSum(int[]p_arr, int n, HashSet<int>q)
{
    for (int i = 0; i < n; i++)
        q.Add(p_arr[i]);
}
 
// Function to check if a range
// can be divided into two equal parts
static void canDivide(int[] p_arr, int n,
            HashSet<int>q, int l, int r)
{
    // To store the value of sum
    // of entire range
    int sum;
 
    if (l == 0)
        sum = p_arr[r];
    else
        sum = p_arr[r] - p_arr[l - 1];
 
    // If value of sum is odd
    if (sum % 2 == 1)
    {
        Console.WriteLine("No");
        return;
    }
 
    // To store p_arr[l-1]
    int beg = 0;
 
    if (l != 0)
        beg = p_arr[l - 1];
 
    // If the value exists in the map
    if(q.Contains(beg + sum / 2) )
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 1, 2, 3 };
    int n = arr.Length;
 
    // prefix-sum array
    int []p_arr = new int[n];
 
    prefixSum(p_arr, arr, n);
 
    // Map to store the values of prefix-sum
    HashSet<int> q = new HashSet<int> ();
 
    qPrefixSum(p_arr, n, q);
 
    // Perform queries
    canDivide(p_arr, n, q, 0, 1);
    canDivide(p_arr, n, q, 1, 3);
    canDivide(p_arr, n, q, 1, 2);
}
}
 
// This code has been contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to find the required prefix sum
function prefixSum(p_arr, arr, n)
{
    p_arr[0] = arr[0];
    for (var i = 1; i < n; i++)
        p_arr[i] = arr[i] + p_arr[i - 1];
}
 
// Function to hash all the values of prefix
// sum array in an unordered map
function hashPrefixSum(p_arr, n, q)
{
    for (var i = 0; i < n; i++)
        q.add(p_arr[i]);
}
 
// Function to check if a range
// can be divided into two equal parts
function canDivide(p_arr, n, q, l, r)
{
    // To store the value of sum
    // of entire range
    var sum;
 
    if (l == 0)
        sum = p_arr[r];
    else
        sum = p_arr[r] - p_arr[l - 1];
 
    // If value of sum is odd
    if (sum % 2 == 1) {
        document.write( "No" );
        return;
    }
 
    // To store p_arr[l-1]
    var beg = 0;
 
    if (l != 0)
        beg = p_arr[l - 1];
 
    // If the value exists in the map
    if (q.has((beg + sum / 2)))
        document.write( "Yes<br>" );
    else
        document.write( "No<br>" );
}
 
// Driver code
var arr = [1, 1, 2, 3 ];
var n = arr.length;
 
// prefix-sum array
var p_arr = Array(n);
prefixSum(p_arr, arr, n);
 
// Map to store the values of prefix-sum
var q = new Set();
hashPrefixSum(p_arr, n, q);
 
// Perform queries
canDivide(p_arr, n, q, 0, 1);
canDivide(p_arr, n, q, 1, 3);
canDivide(p_arr, n, q, 1, 2);
 
</script>

Yes
Yes
No