업데이트가없는 범위 합계 쿼리


난이도 쉽게
자주 묻는 질문 BlackRock GE 헬스 케어 문 프로그 연구소 Synopsys Taxi4Sure 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. 각 쿼리에 대해 왼쪽이 0이면 sumArray [right]를 반환합니다.
  4. 그렇지 않으면 sumArray [right] – sumArray [left – 1]를 반환합니다.

설명

정수와 범위의 배열을 제공했으며 각 쿼리에 대해 주어진 범위 내의 모든 요소의 합계를 알아 내도록 요청 받았습니다. 각 쿼리는 범위의 시작 및 끝 지점 인 범위로 구성됩니다. 이 질문에는 업데이트 쿼리가 포함되지 않습니다. 즉, 쿼리 답변을 찾는 동안 항목을 업데이트 할 필요가 없습니다. 0 인덱스에서 현재 인덱스까지의 모든 요소의 합이 만들어진 배열의 i 번째 위치에 있도록 주어진 배열을 빌드합니다. 이런 식으로 모든 쿼리는 O (n)의 추가 공간과 함께 O (1)에서 해결됩니다.

우리가 만든 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),  sumArray를 계산하려면 O (N)이 필요하고 각 쿼리에 대해 O (1) 시간이 필요하기 때문입니다.

공간 복잡성

주어진 접근 방식에서 우리는 0에서 i까지 요소의 합을 저장하기 위해 새로운 배열 sumArray를 만들었습니다. 따라서이 접근 방식에는 의 위에) 우주. 하지만 원래 배열을 수정할 수도 있습니다. 그러면 공간 복잡성이 일정하게 줄어들 것입니다.