Range Sum Query

Q: 접두사 합 배열이란 무엇인가요?

각 항목이 해당 위치 앞에 있는 모든 값의 합인 배열입니다. 즉, prefix[i] = nums[0] + ... + nums[i-1] 이고, prefix[0] = 0 입니다. 한 번 훑으면서 배열을 만들고 나면, 임의의 범위 [left, right] 의 합을 뺄셈 한 번으로 prefix[right+1] - prefix[left] 처럼 구할 수 있습니다.

Q: 누적 합을 사용한 구간 합 쿼리의 시간 복잡도는 얼마인가요?

접두사 배열을 한 번 만드는 데 O(n) , 쿼리당 O(1) 이므로 q 개의 쿼리에 대해 O(n + q) 입니다. 모든 구간의 값을 직접 더하면 쿼리당 최대 O(n) 이 들어 총 O(n·q) 입니다.

Q: prefix 배열의 항목 수가 nums보다 하나 더 많은 이유는 무엇인가요?

추가된 prefix[0] = 0 은 배열의 비어 있는 시작 부분을 나타냅니다. 이를 사용하면 인덱스 0에서 시작하는 범위를 포함해 모든 범위에 동일한 수식을 적용할 수 있습니다: prefix[right+1] - prefix[0] . 이것이 없으면 left = 0 인 경우를 위한 별도의 분기문이 필요합니다.

Q: 쿼리 사이에 배열이 변경될 수 있다면 어떻게 될까요?

그러면 접두사 배열은 적절한 도구가 아닙니다. 업데이트 하나로 그 뒤의 모든 합계가 바뀌어 이를 복구하는 데 O(n) 의 비용이 들기 때문입니다. 펜윅 트리나 세그먼트 트리는 업데이트와 구간 합을 모두 O(log n) 에 처리합니다. 배열이 절대 바뀌지 않는다면 일반 접두사 합이 더 빠르고 간결합니다.

쉬움누적 합

+10

변경되지 않는 정수 배열 nums와 queries 목록이 주어집니다. 각 쿼리는 0부터 시작하는 인덱스 쌍 [left, right]이며, 양 끝을 포함하여 nums[left] + nums[left+1] + ... + nums[right]의 값을 구합니다. 쿼리와 같은 순서로 답을 반환하세요.

함수

sumRange(nums: integer-array, queries: integer-2d-array) → integer-array

numsinteger-array: 모든 쿼리에 대해 동일한 정수 배열
queriesinteger-2d-array: 더할 범위는 각각 [left, right] 쌍이며, left ≤ right입니다.
반환값integer-array: 각 범위의 합을 쿼리 순서대로 하나씩

제약 조건

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ left ≤ right < nums.length 모든 쿼리 [left, right]에 대해

예제

입력: nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
출력: [6, 0, 1]
설명: 인덱스 0부터 2까지는 3 + (-2) + 5 = 6을 담고 있습니다. 인덱스 1부터 4까지는 -2 + 5 + 1 + (-4) = 0을 담고 있습니다. 범위 [3, 3]은 단일 값 1입니다.

입력: nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
출력: [18, 9, 2, 8]
설명: 배열 전체를 더하면 2 + 7 + 1 + 8 = 18이고, 마지막 두 값을 더하면 1 + 8 = 9이며, 인덱스 0만 더하면 2이고 인덱스 1부터 2까지 더하면 7 + 1 = 8입니다.

제출 시 숨은 테스트 +14개

후속 질문

이제 숫자들이 격자를 이루고, 각 쿼리는 두 모서리로 지정된 직사각형의 합을 묻습니다. 각 쿼리에 일정한 횟수의 연산으로 답할 수 있도록 누적 합을 어떻게 확장하면 좋을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

하나의 구간이 하나의 반복문입니다. 문제는 구간의 개수입니다. 각 쿼리가 배열 대부분을 포함할 수 있으므로, 각 구간을 따로 더하면 같은 덧셈을 계속 반복하게 됩니다. 모든 값을 한 번만 더해 누적 합을 구하면 각 구간은 뺄셈 한 번으로 처리할 수 있습니다.

각 범위를 더하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

각 질의에 독립적으로 답하세요. 합계를 0으로 시작하고, nums[left]부터 nums[right]까지 더한 다음 결과를 저장하세요. [3, -2, 5, 1, -4, 6]에서 [1, 4]의 경우 -2 + 5 + 1 + (-4) = 0입니다.

이 방법은 정확하며, 질의가 하나뿐이라면 최선의 방법입니다. 범위에 있는 모든 값을 한 번씩 읽어야 하기 때문입니다. 비용은 반복에 있습니다. 하나의 질의가 최대 n개의 값을 포함할 수 있으므로, q개의 질의에는 최대 n × q번의 덧셈이 필요합니다. n = 10^4이고 배열의 대부분을 포함하는 질의가 1500개라면, 약 1.3 × 10^7번의 덧셈이 필요하며, 그중 대부분은 이전 질의에서 수행한 작업을 반복하는 것입니다.

결과 목록 외에는 합계 하나만 유지하므로 추가 공간은 O(1)입니다.

알고리즘

빈 답변 목록을 만듭니다.
각 쿼리 [left, right]에 대해 total = 0으로 설정합니다.
left부터 right까지 양 끝을 포함하여 모든 i에 대해 nums[i]를 total에 더합니다.
total을 답변 목록에 추가하고, 마지막 쿼리 이후에 답변 목록을 반환합니다.

def sumRange(nums, queries):
    answers = []
    for left, right in queries:
        total = 0
        for i in range(left, right + 1):
            total += nums[i]
        answers.append(total)
    return answers

누적 합

핵심 아이디어

prefix[i]를 처음 i개 값의 합이라고 하자. 시작 부분이 비어 있을 때는 prefix[0] = 0이다. [3, -2, 5, 1, -4, 6]의 경우 prefix = [0, 3, 1, 6, 7, 3, 9]가 된다. 각 항목은 바로 앞 항목에 값 하나를 더한 것이므로, 전체 배열을 만드는 데 n번의 덧셈이 필요하다.

범위 [left, right]의 합은 인덱스 right까지 포함한 모든 값의 합에서 인덱스 left 이전까지의 모든 값의 합을 뺀 것이다. 즉 prefix[right+1] - prefix[left]이다. [1, 4]의 경우: prefix[5] - prefix[1] = 3 - 3 = 0. [0, 2]의 경우: prefix[3] - prefix[0] = 6 - 0 = 6. 앞에 있는 0 덕분에 인덱스 0에서 시작하는 범위도 별도의 예외 처리 없이 계산할 수 있다.

배열을 만드는 데 O(n)이 들고, 각 질의에는 뺄셈 한 번만 필요하므로 전체 시간 복잡도는 O(n + q)이고 추가 공간 복잡도는 O(n)이다. 여기서 어떤 누적 합도 크기가 10^4 × 10^4 = 10^8을 넘지 않으므로 32비트 정수면 충분하다.

알고리즘

길이가 n+1이고 prefix[0] = 0인 prefix를 만듭니다.
0부터 n-1까지 각 i에 대해 prefix[i+1] = prefix[i] + nums[i]로 설정합니다.
각 쿼리 [left, right]에 대해 prefix[right+1] - prefix[left]를 답 목록에 추가합니다.
답 목록을 반환합니다.

def sumRange(nums, queries):
    # prefix[i] is the sum of the first i values, so prefix[0] = 0.
    prefix = [0] * (len(nums) + 1)
    for i, value in enumerate(nums):
        prefix[i + 1] = prefix[i] + value
    # nums[left..right] is the first right+1 values minus the first left values.
    return [prefix[right + 1] - prefix[left] for left, right in queries]

함정과 경계 사례

여기서 거의 모든 버그는 인덱스가 1만큼 어긋난 것입니다.

prefix[right] - prefix[left]를 작성하는 경우입니다. prefix[0] = 0이면 nums[right]가 빠지므로, 범위 [3, 3]의 결과는 인덱스 3의 값이 아니라 0이 됩니다.
prefix를 nums와 길이가 같게 만들어 prefix[i]에 nums[i]가 포함되는 경우입니다. 그러면 0에서 시작하는 범위에는 prefix[left-1]이 필요한데, 이는 범위를 벗어나며 Python에서는 조용히 마지막 항목을 읽습니다. 앞에 0을 하나 추가하면 이 특수한 경우가 사라집니다.
브루트 포스 반복을 i < right에서 끝내는 경우입니다. 범위의 양 끝이 모두 포함됩니다.
Lua와 R에서는 1부터 센다는 점을 잊는 경우입니다. 0부터 세는 쿼리 [left, right]는 해당 언어에서 nums[left+1]부터 nums[right+1]까지를 포함하며, 접두 합의 차이도 같은 방식으로 이동합니다.
값이나 길이가 커질 때 32비트 합계를 사용하는 경우입니다. 여기서 가장 큰 합은 10^8이지만, 10^9에 가까운 값에서는 접두 합이 빠르게 오버플로되므로 64비트 배열을 기본으로 사용하는 것이 안전합니다.

자주 묻는 질문4

접두사 합 배열이란 무엇인가요?

각 항목이 해당 위치 앞에 있는 모든 값의 합인 배열입니다. 즉, prefix[i] = nums[0] + ... + nums[i-1]이고, prefix[0] = 0입니다. 한 번 훑으면서 배열을 만들고 나면, 임의의 범위 [left, right]의 합을 뺄셈 한 번으로 prefix[right+1] - prefix[left]처럼 구할 수 있습니다.

누적 합을 사용한 구간 합 쿼리의 시간 복잡도는 얼마인가요?

접두사 배열을 한 번 만드는 데 O(n), 쿼리당 O(1)이므로 q개의 쿼리에 대해 O(n + q)입니다. 모든 구간의 값을 직접 더하면 쿼리당 최대 O(n)이 들어 총 O(n·q)입니다.

prefix 배열의 항목 수가 nums보다 하나 더 많은 이유는 무엇인가요?

추가된 prefix[0] = 0은 배열의 비어 있는 시작 부분을 나타냅니다. 이를 사용하면 인덱스 0에서 시작하는 범위를 포함해 모든 범위에 동일한 수식을 적용할 수 있습니다: prefix[right+1] - prefix[0]. 이것이 없으면 left = 0인 경우를 위한 별도의 분기문이 필요합니다.

쿼리 사이에 배열이 변경될 수 있다면 어떻게 될까요?

그러면 접두사 배열은 적절한 도구가 아닙니다. 업데이트 하나로 그 뒤의 모든 합계가 바뀌어 이를 복구하는 데 O(n)의 비용이 들기 때문입니다. 펜윅 트리나 세그먼트 트리는 업데이트와 구간 합을 모두 O(log n)에 처리합니다. 배열이 절대 바뀌지 않는다면 일반 접두사 합이 더 빠르고 간결합니다.

Python

def sumRange(nums, queries):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3]]

기대값

[6, 0, 1]