Range Sum Query
변하지 않는 정수 배열 nums와 queries 목록이 주어집니다. 각 쿼리는 0부터 시작하는 인덱스 쌍 [left, right]이며, 양 끝 인덱스를 모두 포함하여 nums[left] + nums[left+1] + ... + nums[right]의 값을 구합니다. 쿼리와 같은 순서로 답을 반환하세요.
함수
- numsinteger-array
- 모든 쿼리에서 동일한 정수 배열
- queriesinteger-2d-array
- 합산할 범위들로, 각 범위는 left ≤ right인 [left, right] 쌍입니다
- 반환값integer-array
- 각 범위의 합을 쿼리 순서대로 하나씩
제약 조건
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ 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]
- 설명
- 배열 전체의 합은
18이고, 마지막 두 값의 합은1 + 8 = 9이며, 인덱스 0만의 값은2, 인덱스 1부터 2까지의 합은7 + 1 = 8입니다.
후속 질문
숫자들이 격자를 이루고 각 질의가 직사각형의 합을 묻는다면, 각 질의에 상수 시간으로 답할 수 있도록 누적 합을 어떻게 확장할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
많은 쿼리는 거의 동일한 값을 다룹니다. 쿼리를 읽기 전에 한 번만 해 둘 수 있는 작업은 무엇일까요?
모든
i에 대해 처음i개 값의 합계를 알고 있다면, 구간의 합은 그 합계 두 개의 차이가 됩니다.prefix를prefix[0] = 0및prefix[i+1] = prefix[i] + nums[i]로 만드세요. 그러면 각 쿼리[left, right]는prefix[right+1] - prefix[left]입니다.
풀이
하나의 구간은 반복문이지만, 각 쿼리가 배열의 대부분을 포함할 수 있으므로 각 구간을 따로 합산하면 같은 덧셈을 반복하게 됩니다. 배열을 한 번 누적해 누적 합을 만들면 모든 구간을 한 번의 뺄셈으로 처리할 수 있습니다.
각 범위를 더하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
각 쿼리마다 nums[left]부터 nums[right]까지를 합계에 더합니다. 범위 내의 모든 값을 읽으므로 올바른 방법이며, 쿼리 하나에 대해서는 이것이 최선입니다. 쿼리 하나가 최대 n개의 값을 포함할 수 있으므로, q개의 쿼리에는 최대 n × q번의 덧셈이 필요합니다. n = 10^4이고 q = 1500일 때 1.5 × 10^7번이며, 그 대부분은 반복 작업입니다.
알고리즘
- 빈 답변 목록을 만듭니다.
- 각 쿼리
[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]의 경우 [0, 3, 1, 6, 7, 3, 9]가 된다.
범위 [left, right]의 합은 인덱스 right까지의 모든 값에서 인덱스 left 이전의 모든 값을 뺀 것이다. 즉, prefix[right+1] - prefix[left]이다. [1, 4]의 경우 prefix[5] - prefix[1] = 3 - 3 = 0이다. 맨 앞의 0이 있으면 인덱스 0에서 시작하는 범위에도 같은 공식을 사용할 수 있다. n번 더하는 한 번의 순회로 배열을 만들고, 각 쿼리는 뺄셈 한 번으로 처리한다.
알고리즘
- 길이가
n+1인prefix를 만들고prefix[0] = 0으로 설정합니다. 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]
함정과 경계 사례
prefix[right] - prefix[left]를 작성하는 것.prefix[0] = 0이면nums[right]가 제외되므로, 범위[3, 3]의 결과가1이 아니라0이 됩니다.prefix의 길이를nums와 같게 만들어prefix[i]에nums[i]가 포함되도록 하는 것. 그러면 0에서 시작하는 범위는prefix[-1]이 필요한데, 이는 범위를 벗어나며 Python은 조용히 마지막 항목을 읽습니다.- 브루트 포스 루프를
i < right에서 멈추는 것. 양쪽 끝이 모두 포함되므로[3, 3]의 합은 0이 됩니다. - 1부터 세는 Lua와 R에서는 0 기반 질의
[left, right]가nums[left+1]부터nums[right+1]까지를 포함하며, 접두사 인덱스도 같은 방식으로 이동합니다.
자주 묻는 질문3
누적합 배열이란 무엇인가요?
각 항목이 해당 위치 이전의 모든 값의 합인 배열입니다: 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)이 듭니다.
쿼리 사이에 배열이 바뀔 수 있다면 어떻게 될까요?
따라서 접두사 배열은 적절한 도구가 아닙니다. 한 번 업데이트하면 그 이후의 모든 합계가 이동하고 이를 수정하는 데 O(n)이 들기 때문입니다. 펜윅 트리나 세그먼트 트리는 업데이트와 구간 합 모두를 O(log n)에 처리합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def sumRange(nums, queries):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자들
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
예상 출력
[6, 0, 1]