范围总和查询,无更新


难度级别 易得奖学金
经常问 贝莱德 GE医疗集团 月蛙实验室 新思 出租车 Twilio
排列 拉森和图布罗 查询问题

问题陈述

问题“不更新的范围总和查询”表明您有一个 排列 of 整数 和一个范围。 问题陈述要求找出给定范围内所有元素的总和。

使用案列

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

说明

范围(0,4)之间的所有数字之和为40,范围(1,3)之间的所有数字之和为24。

范围总和查询,无更新

 

算法

  1. 创建一个大小与给定数组相同的数组sumArray。
  2. 遍历给定数组,并将sumArray的上一个元素与当前数组的当前元素之和存储,并将其存储到sumArray中。
  3. 对于每个查询,如果left等于0,则返回sumArray [right],
  4. 否则返回sumArray [right] – sumArray [left – 1]。

说明

我们给出了一个整数数组和一个范围,并要求我们为每个查询找出给定范围内所有元素的总和。 每个查询都包含一个范围,作为范围的起点和终点。 此问题不涉及任何更新查询。 这意味着在查找查询答案时无需更新任何内容。 我们将只构建给定的数组,以使从0索引到当前索引的所有元素的总和位于所构建数组的第i个位置。 这样,每个查询将在O(1)中得到解决,并留有O(n)的额外空间。

我们将构建我们创建的sumArray。 在此sumArray中,从0到i的元素之和将存储在sumArray的第i个位置。 我们将进行计算,因为我们将把sumArray的先前值与给定数组的当前值相加,并在遍历时将其存储到sumArray的当前索引位置。 因此,当有人问这个位置上所有数字的总和是多少时,我们只需要为每个唯一的数组元素返回该位置的值即可。

当我们收到由任意范围组成的查询时,如果发现范围的左边或起点等于0,则只返回上面我们讨论的sumArray [right]的值,左边的范围是不等于0,我们将返回sumArray [right]和sumArray [left-1]之差。 这些将是必需的答案。 这种方法也是我们使用的最简单的方法之一 动态编程.

代码

范围总和查询的C ++代码,无需更新

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

范围和查询的Java代码,无需更新

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

复杂度分析

时间复杂度

O(N + Q),  因为我们需要O(N)来计算sumArray,然后才需要每个查询的O(1)时间。

空间复杂度

在这里,在给定的方法中,我们创建了一个新的数组sumArray来存储从0到i的元素之和。 因此,这种方法需要 上) 空间。 但是我们也可以修改原始数组。 然后,空间复杂度将降低为常数。