Consultas de suma de rango sin actualizaciones

Dada una array arr de enteros de tamaño n. Necesitamos calcular la suma de elementos del índice i al índice j. Las consultas que consisten en valores de índice i y j se ejecutarán varias veces.

Ejemplos: 

Input : arr[] = {1, 2, 3, 4, 5}
        i = 1, j = 3
        i = 2, j = 4
Output :  9
         12         

Input : arr[] = {1, 2, 3, 4, 5}
        i = 0, j = 4 
        i = 1, j = 2 
Output : 15
          5

Una solución simple es calcular la suma de cada consulta.

Una solución eficiente es precalcular la suma del prefijo. Deje que pre[i] almacene la suma de elementos de arr[0] a arr[i]. Para responder una consulta (i, j), devolvemos pre[j] – pre[i-1].

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

// CPP program to find sum between two indexes
// when there is no update.
#include <bits/stdc++.h>
using namespace std;
 
void preCompute(int arr[], int n, int pre[])
{
    pre[0] = arr[0];
    for (int i = 1; i < n; i++)
        pre[i] = arr[i] + pre[i - 1];
}
 
// Returns sum of elements in arr[i..j]
// It is assumed that i <= j
int rangeSum(int i, int j, int pre[])
{
    if (i == 0)
        return pre[j];
 
    return pre[j] - pre[i - 1];
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    int pre[n];
   
    // Function call
    preCompute(arr, n, pre);
    cout << rangeSum(1, 3, pre) << endl;
    cout << rangeSum(2, 4, pre) << endl;
 
    return 0;
}

// Java program to find sum between two indexes
// when there is no update.
 
import java.util.*;
import java.lang.*;
 
class GFG {
    public static void preCompute(int arr[], int n,
                                  int pre[])
    {
        pre[0] = arr[0];
        for (int i = 1; i < n; i++)
            pre[i] = arr[i] + pre[i - 1];
    }
 
    // Returns sum of elements in arr[i..j]
    // It is assumed that i <= j
    public static int rangeSum(int i, int j, int pre[])
    {
        if (i == 0)
            return pre[j];
 
        return pre[j] - pre[i - 1];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        int n = arr.length;
 
        int pre[] = new int[n];
 
        preCompute(arr, n, pre);
        System.out.println(rangeSum(1, 3, pre));
        System.out.println(rangeSum(2, 4, pre));
    }
}
 
// Code Contributed by Mohit Gupta_OMG <(0_o)>

# Python program to find sum between two indexes
# when there is no update.
 
# Function to compute prefix sum
def preCompute(arr, n, prefix):
  prefix[0] = arr[0]
  for i in range(1, n):
    prefix[i] = prefix[i - 1] + arr[i]
 
# Returns sum of elements in arr[i..j]
# It is assumed that i <= j
def rangeSum(l, r):
  if l == 0:
    print(prefix[r])
    return
   
  print(prefix[r] - prefix[l - 1])
     
# Driver code
arr = [1, 2, 3, 4, 5]
n = len(arr)
prefix = [0 for i in range(n)]
 
# preComputation
preCompute(arr, n, prefix)
 
# Range Queries
rangeSum(1, 3)
rangeSum(2, 4)
 
# This code is contributed by dineshdkda31.

// Program to find sum between two
// indexes when there is no update.
using System;
 
class GFG {
    public static void preCompute(int[] arr, int n,
                                  int[] pre)
    {
        pre[0] = arr[0];
        for (int i = 1; i < n; i++)
            pre[i] = arr[i] + pre[i - 1];
    }
 
    // Returns sum of elements in
    // arr[i..j]
    // It is assumed that i <= j
    public static int rangeSum(int i, int j, int[] pre)
    {
        if (i == 0)
            return pre[j];
 
        return pre[j] - pre[i - 1];
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int n = arr.Length;
 
        int[] pre = new int[n];
 
        // Function call
        preCompute(arr, n, pre);
        Console.WriteLine(rangeSum(1, 3, pre));
        Console.WriteLine(rangeSum(2, 4, pre));
    }
}
 
// Code Contributed by Anant Agarwal.

<script>
 
// JavaScript Program to find sum between two
// indexes when there is no update.
 
let pre = new Array(1000,0);
 
function preCompute(arr, n)
{
    pre[0] = arr[0];
    for (let i = 1; i < n; i++)
        pre[i] = arr[i] + pre[i - 1];
}
 
// Returns sum of elements in
// arr[i..j]
// It is assumed that i <= j
function rangeSum(i, j, pre)
{
    if (i == 0)
        return pre[j];
 
    return pre[j] - pre[i - 1];
}
 
// Driver code
let arr = [1, 2, 3, 4, 5];
let n = arr.length;
   
// Function call
preCompute(arr, n);
 
document.write(rangeSum(1, 3, pre)+"<br>");
document.write(rangeSum(2, 4, pre));
 
</script>

9
12

Aquí la complejidad de tiempo de cada consulta de suma de rango es O(1) y la complejidad de tiempo general es O(n).

Espacio auxiliar requerido = O(n) , donde n es el tamaño de la array dada.

La pregunta se complica cuando también se permiten actualizaciones. En tales situaciones, cuando se utilizan estructuras de datos avanzadas como Segment Tree o Binary Indexed Tree .

Este artículo es una contribución de Rahul Chawla . 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.