Suma máxima de prefijos para un rango dado

Dada una array de n enteros y q consultas, cada consulta tiene un rango de l a r. Encuentre la suma máxima de prefijos para el rango l – r.

Ejemplos: 

Input: a[] = {-1, 2, 3, -5} 
       q = 2
       l = 0, r = 3
       l = 1, r = 3

Output: 4
        5

Explanation:- The range (0, 3) in the 1st query has
              [-1, 2, 3, -5], since it is prefix, 
              we have to start from -1. Hence, the 
              max prefix sum will be -1 + 2 + 3 = 4.
              The range (1, 3) in the 2nd query has 
              [2, 3, -5], since it is prefix, we 
              have to start from 2. Hence, the max
              prefix sum will be 2 + 3 = 5.

Input: a[] = {-2, -3, 4, -1, -2, 1, 5, -3} 
       q = 1
       l = 1 r = 7 

Output: 4

Explanation:- The range (1, 7) in the 1st query has 
              [-3, 4, -1, -2, 1, 5, -3], since it is
              prefix, we have to start from -3. 
              Hence, the max prefix sum will be 
              -3 + 4 - 1 - 2 + 1 + 5 = 4.

Enfoque normal:   una solución simple es ejecutar un ciclo de l a r y calcular la suma máxima de prefijos de l a r para cada consulta.

Complejidad de Tiempo: O(q * n), 
Espacio Auxiliar: O(1)

Enfoque eficiente: 

Un enfoque eficiente será construir un árbol de segmentos donde cada Node almacene dos valores (sum y prefix_sum) y hacer una consulta de rango en él para encontrar la suma máxima de prefijos. Pero para construir el árbol de segmentos tenemos que pensar qué almacenar en los Nodes del árbol. 

Para encontrar la suma máxima del prefijo, necesitaremos dos cosas, una es la suma y la otra la suma del prefijo. La fusión devolverá dos cosas, la suma de los rangos y la suma del prefijo que almacenará el máximo (prefijo.izquierda, prefijo.sum + prefijo.derecha) en el árbol de segmentos.

Si lo analizamos en profundidad, la suma máxima de prefijos para cualquier combinación de dos rangos será la suma de prefijos del lado izquierdo o la suma del lado izquierdo + la suma del prefijo del lado derecho, lo que sea máximo se tendrá en cuenta. 

Representación de árboles de segmentos:

  1. Los Nodes hoja son los elementos de la array de entrada. 
  2. Cada Node interno representa alguna fusión de los Nodes hoja. La fusión puede ser diferente para diferentes problemas. Para este problema, la fusión es la suma de hojas debajo de un Node.

Se utiliza una representación de array de árbol para representar árboles de segmento. Para cada Node en el índice i, el hijo izquierdo está en el índice 2*i+1 , el hijo derecho en 2*i+2 y el padre está en (i-1)/2.

Construcción del árbol de segmentos a partir de una array dada:

Empezamos con un segmento arr[0 . . . n-1]. y cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), y luego llamamos al mismo procedimiento en ambas mitades, y para cada segmento, almacenamos la suma y el prefijo sum en correspondiente Node.

Luego hacemos una consulta de rango en el árbol de segmentos para averiguar la suma máxima de prefijos para el rango dado y generamos la suma máxima de prefijos.

A continuación se muestra la implementación en C++ del enfoque anterior. 

CPP

// CPP program to find
// maximum prefix sum
#include <bits/stdc++.h>
using namespace std;
 
// struct two store two values in one node
struct Node {
    int sum;
    int prefix;
};
 
Node tree[4 * 10000];
 
// function to build the segment tree
void build(int a[], int index, int beg, int end)
{
    if (beg == end) {
 
        // If there is one element in array,
        // store it in current node of
        // segment tree
        tree[index].sum = a[beg];
        tree[index].prefix = a[beg];
    } else {
        int mid = (beg + end) / 2;
 
        // If there are more than one elements,
        // then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid);
        build(a, 2 * index + 2, mid + 1, end);
 
        // adds the sum and stores in the index
        // position of segment tree
        tree[index].sum = tree[2 * index + 1].sum +
                          tree[2 * index + 2].sum;
 
        // stores the max of prefix-sum either
        // from right or from left.
        tree[index].prefix = max(tree[2 * index + 1].prefix,
                                 tree[2 * index + 1].sum +
                                tree[2 * index + 2].prefix);
    }
}
 
// function to do the range query in the segment
// tree for the maximum prefix sum
Node query(int index, int beg, int end, int l, int r)
{
    Node result;
    result.sum = result.prefix = -1;
 
    // If segment of this node is outside the given
    // range, then return the minimum value.
    if (beg > r || end < l)
        return result;
 
    // If segment of this node is a part of given
    // range, then return the node of the segment
    if (beg >= l && end <= r)
        return tree[index];
 
    int mid = (beg + end) / 2;
 
    // if left segment of this node falls out of
    // range, then recur in the right side of
    // the tree
    if (l > mid)
        return query(2 * index + 2, mid + 1, end,
                                         l, r);
 
    // if right segment of this node falls out of
    // range, then recur in the left side of
    // the tree
    if (r <= mid)
        return query(2 * index + 1, beg, mid,
                                       l, r);
 
    // If a part of this segment overlaps with
    // the given range
    Node left = query(2 * index + 1, beg, mid,
                                        l, r);
    Node right = query(2 * index + 2, mid + 1,
                                   end, l, r);
 
    // adds the sum of the left and right
    // segment
    result.sum = left.sum + right.sum;
 
    // stores the max of prefix-sum
    result.prefix = max(left.prefix, left.sum +
                            right.prefix);
 
    // returns the value
    return result;
}
 
// driver program to test the program
int main()
{
 
    int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
 
    // calculates the length of array
    int n = sizeof(a) / sizeof(a[0]);
 
    // calls the build function to build
    // the segment tree
    build(a, 0, 0, n - 1);
 
    // find the max prefix-sum between
    // 3rd and 5th index of array
    cout << query(0, 0, n - 1, 3, 5).prefix
         << endl;
 
    // find the max prefix-sum between
    // 0th and 7th index of array
    cout << query(0, 0, n - 1, 1, 7).prefix
         << endl;
 
    return 0;
}

Java

// JAVA program to find
// maximum prefix sum
class GFG
{
 
// two store two values in one node
static class Node
{
    int sum;
    int prefix;
};
 
static Node []tree = new Node[4 * 10000];
static
{
    for(int i = 0; i < tree.length; i++)
        tree[i] = new Node();
}
 
// function to build the segment tree
static void build(int a[], int index, int beg, int end)
{
    if (beg == end)
    {
 
        // If there is one element in array,
        // store it in current node of
        // segment tree
        tree[index].sum = a[beg];
        tree[index].prefix = a[beg];
    } else {
        int mid = (beg + end) / 2;
 
        // If there are more than one elements,
        // then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid);
        build(a, 2 * index + 2, mid + 1, end);
 
        // adds the sum and stores in the index
        // position of segment tree
        tree[index].sum = tree[2 * index + 1].sum +
                        tree[2 * index + 2].sum;
 
        // stores the max of prefix-sum either
        // from right or from left.
        tree[index].prefix = Math.max(tree[2 * index + 1].prefix,
                                tree[2 * index + 1].sum +
                                tree[2 * index + 2].prefix);
    }
}
 
// function to do the range query in the segment
// tree for the maximum prefix sum
static Node query(int index, int beg, int end, int l, int r)
{
    Node result = new Node();
    result.sum = result.prefix = -1;
 
    // If segment of this node is outside the given
    // range, then return the minimum value.
    if (beg > r || end < l)
        return result;
 
    // If segment of this node is a part of given
    // range, then return the node of the segment
    if (beg >= l && end <= r)
        return tree[index];
 
    int mid = (beg + end) / 2;
 
    // if left segment of this node falls out of
    // range, then recur in the right side of
    // the tree
    if (l > mid)
        return query(2 * index + 2, mid + 1, end,
                                        l, r);
 
    // if right segment of this node falls out of
    // range, then recur in the left side of
    // the tree
    if (r <= mid)
        return query(2 * index + 1, beg, mid,
                                    l, r);
 
    // If a part of this segment overlaps with
    // the given range
    Node left = query(2 * index + 1, beg, mid,
                                        l, r);
    Node right = query(2 * index + 2, mid + 1,
                                end, l, r);
 
    // adds the sum of the left and right
    // segment
    result.sum = left.sum + right.sum;
 
    // stores the max of prefix-sum
    result.prefix = Math.max(left.prefix, left.sum +
                            right.prefix);
 
    // returns the value
    return result;
}
 
// Driver code
public static void main(String[] args)
{
 
    int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
 
    // calculates the length of array
    int n = a.length;
 
    // calls the build function to build
    // the segment tree
    build(a, 0, 0, n - 1);
 
    // find the max prefix-sum between
    // 3rd and 5th index of array
    System.out.print(query(0, 0, n - 1, 3, 5).prefix
        +"\n");
 
    // find the max prefix-sum between
    // 0th and 7th index of array
    System.out.print(query(0, 0, n - 1, 1, 7).prefix
        +"\n");
}
}
 
// This code is contributed by PrinciRaj1992

C#

// C# program to find
// maximum prefix sum
using System;
 
class GFG
{
 
// two store two values in one node
class Node
{
    public int sum;
    public int prefix;
};
 
static Node []tree = new Node[4 * 10000];
 
// function to build the segment tree
static void build(int []a, int index, int beg, int end)
{
    if (beg == end)
    {
 
        // If there is one element in array,
        // store it in current node of
        // segment tree
        tree[index].sum = a[beg];
        tree[index].prefix = a[beg];
    } else {
        int mid = (beg + end) / 2;
 
        // If there are more than one elements,
        // then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid);
        build(a, 2 * index + 2, mid + 1, end);
 
        // adds the sum and stores in the index
        // position of segment tree
        tree[index].sum = tree[2 * index + 1].sum +
                        tree[2 * index + 2].sum;
 
        // stores the max of prefix-sum either
        // from right or from left.
        tree[index].prefix = Math.Max(tree[2 * index + 1].prefix,
                                tree[2 * index + 1].sum +
                                tree[2 * index + 2].prefix);
    }
}
 
// function to do the range query in the segment
// tree for the maximum prefix sum
static Node query(int index, int beg, int end, int l, int r)
{
    Node result = new Node();
    result.sum = result.prefix = -1;
 
    // If segment of this node is outside the given
    // range, then return the minimum value.
    if (beg > r || end < l)
        return result;
 
    // If segment of this node is a part of given
    // range, then return the node of the segment
    if (beg >= l && end <= r)
        return tree[index];
 
    int mid = (beg + end) / 2;
 
    // if left segment of this node falls out of
    // range, then recur in the right side of
    // the tree
    if (l > mid)
        return query(2 * index + 2, mid + 1, end,
                                        l, r);
 
    // if right segment of this node falls out of
    // range, then recur in the left side of
    // the tree
    if (r <= mid)
        return query(2 * index + 1, beg, mid,
                                    l, r);
 
    // If a part of this segment overlaps with
    // the given range
    Node left = query(2 * index + 1, beg, mid,
                                        l, r);
    Node right = query(2 * index + 2, mid + 1,
                                end, l, r);
 
    // adds the sum of the left and right
    // segment
    result.sum = left.sum + right.sum;
 
    // stores the max of prefix-sum
    result.prefix = Math.Max(left.prefix, left.sum +
                            right.prefix);
 
    // returns the value
    return result;
}
 
// Driver code
public static void Main(String[] args)
{
 
    for(int i = 0; i < tree.Length; i++)
        tree[i] = new Node();
    int []a = { -2, -3, 4, -1, -2, 1, 5, -3 };
 
    // calculates the length of array
    int n = a.Length;
 
    // calls the build function to build
    // the segment tree
    build(a, 0, 0, n - 1);
 
    // find the max prefix-sum between
    // 3rd and 5th index of array
    Console.Write(query(0, 0, n - 1, 3, 5).prefix
        +"\n");
 
    // find the max prefix-sum between
    // 0th and 7th index of array
    Console.Write(query(0, 0, n - 1, 1, 7).prefix
        +"\n");
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to find
# maximum prefix sum
 
# struct two store two values in one node
 
# function to build the segment tree
def build(a, index, beg, end):
    global tree
 
    if (beg == end):
 
        # If there is one element in array,
        # store it in current node of
        # segment tree
        tree[index][0] = a[beg]
        tree[index][1] = a[beg]
    else:
        mid = (beg + end) // 2
 
        # If there are more than one elements,
        # then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid)
        build(a, 2 * index + 2, mid + 1, end)
 
        # adds the sum and stores in the index
        # position of segment tree
        tree[index][0] = tree[2 * index + 1][0] + tree[2 * index + 2][0]
 
        # stores the max of prefix-sum either
        # from right or from left.
        tree[index][1] = max(tree[2 * index + 1][1],tree[2 * index + 1][0] + tree[2 * index + 2][1])
 
# function to do the range query in the segment
# tree for the maximum prefix sum
def query(index, beg, end, l, r):
    global tree
    result = [-1, -1]
    # result[0] = result[1] = -1
 
    # If segment of this node is outside the given
    # range, then return the minimum value.
    if (beg > r or end < l):
        return result
 
    # If segment of this node is a part of given
    # range, then return the node of the segment
    if (beg >= l and end <= r):
        return tree[index]
 
    mid = (beg + end) // 2
 
    # if left segment of this node falls out of
    # range, then recur in the right side of
    # the tree
    if (l > mid):
        return query(2 * index + 2, mid + 1, end, l, r)
 
    # if right segment of this node falls out of
    # range, then recur in the left side of
    # the tree
    if (r <= mid):
        return query(2 * index + 1, beg, mid, l, r)
 
    # If a part of this segment overlaps with
    # the given range
    left = query(2 * index + 1, beg, mid, l, r)
    right = query(2 * index + 2, mid + 1, end, l, r)
 
    # adds the sum of the left and right
    # segment
    result[0] = left[0] + right[0]
 
    # stores the max of prefix-sum
    result[1] = max(left[1], left[0] + right[1])
 
    # returns the value
    return result
 
 
# driver program to test the program
if __name__ == '__main__':
 
    a = [-2, -3, 4, -1, -2, 1, 5, -3 ]
 
    tree = [[0,0] for i in range(4 * 10000)]
 
    # calculates the length of array
    n = len(a)
 
    # calls the build function to build
    # the segment tree
    build(a, 0, 0, n - 1)
 
    # find the max prefix-sum between
    # 3rd and 5th index of array
    print(query(0, 0, n - 1, 3, 5)[1])
 
    # find the max prefix-sum between
    # 0th and 7th index of array
    print(query(0, 0, n - 1, 1, 7)[1])
 
    # This code is contributed by mohit kumar 29.

Javascript

<script>
 
// JavaScript program to find
// maximum prefix sum
     
    // two store two values in one node
    class Node
    {
        constructor()
        {
            let sum,prefix;
        }
    }
     
    let tree=new Array(4 * 10000);
    for(let i = 0; i < tree.length; i++)
        tree[i] = new Node();
     
    // function to build the segment tree
    function build(a,index,beg,end)
    {
        if (beg == end)
    {
  
        // If there is one element in array,
        // store it in current node of
        // segment tree
        tree[index].sum = a[beg];
        tree[index].prefix = a[beg];
    } else {
        let mid = Math.floor((beg + end) / 2);
  
        // If there are more than one elements,
        // then recur for left and right subtrees
        build(a, 2 * index + 1, beg, mid);
        build(a, 2 * index + 2, mid + 1, end);
  
        // adds the sum and stores in the index
        // position of segment tree
        tree[index].sum = tree[2 * index + 1].sum +
                        tree[2 * index + 2].sum;
  
        // stores the max of prefix-sum either
        // from right or from left.
        tree[index].prefix =
        Math.max(tree[2 * index + 1].prefix,
        tree[2 * index + 1].sum +
        tree[2 * index + 2].prefix);
    }
    }
     
    // function to do the range query in the segment
// tree for the maximum prefix sum
    function query(index,beg,end,l,r)
    {
        let result = new Node();
    result.sum = result.prefix = -1;
  
    // If segment of this node is outside the given
    // range, then return the minimum value.
    if (beg > r || end < l)
        return result;
  
    // If segment of this node is a part of given
    // range, then return the node of the segment
    if (beg >= l && end <= r)
        return tree[index];
  
    let mid = Math.floor((beg + end) / 2);
  
    // if left segment of this node falls out of
    // range, then recur in the right side of
    // the tree
    if (l > mid)
        return query(2 * index + 2, mid + 1, end,
                                        l, r);
  
    // if right segment of this node falls out of
    // range, then recur in the left side of
    // the tree
    if (r <= mid)
        return query(2 * index + 1, beg, mid,
                                    l, r);
  
    // If a part of this segment overlaps with
    // the given range
    let left = query(2 * index + 1, beg, mid,
                                        l, r);
    let right = query(2 * index + 2, mid + 1,
                                end, l, r);
  
    // adds the sum of the left and right
    // segment
    result.sum = left.sum + right.sum;
  
    // stores the max of prefix-sum
    result.prefix = Math.max(left.prefix, left.sum +
                            right.prefix);
  
    // returns the value
    return result;
    }
     
     
    // Driver code
    let a=[-2, -3, 4, -1, -2, 1, 5, -3];
    // calculates the length of array
    let n = a.length;
  
    // calls the build function to build
    // the segment tree
    build(a, 0, 0, n - 1);
  
    // find the max prefix-sum between
    // 3rd and 5th index of array
    document.write(query(0, 0, n - 1, 3, 5).prefix
        +"<br>");
  
    // find the max prefix-sum between
    // 0th and 7th index of array
    document.write(query(0, 0, n - 1, 1, 7).prefix
        +"<br>");
     
 
// This code is contributed by patel2127
 
</script>
Producción

-1
4

Complejidad del tiempo: 

La complejidad del tiempo para la construcción del árbol es O(n) . Hay un total de 2n-1 Nodes, y el valor de cada Node se calcula solo una vez en la construcción del árbol.
La complejidad del tiempo para cada consulta es O (log n).
La complejidad temporal del problema es O(q * log n)

Este artículo es una contribución de Raja Vikramaditya . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *