구간 합(Range Sum)이란?

구간 합은 배열의 특정 구간에 있는 원소들의 합을 구하는 연산이다. 예를 들어, 배열 [2, 5, 1, 4, 3, 6]에서 인덱스 1부터 4까지의 구간 합은 5 + 1 + 4 + 3 = 13이다.

예시

다음 배열을 예시로 구간합을 구해보겠다:

인덱스 0 1 2 3 4 5
값 2 5 1 4 3 6

여러 구간 합의 예시:

구간 합을 구하는 방법

1. 단순 반복문 방식

def range_sum(arr, start, end):
    sum = 0
    for i in range(start, end + 1):
        sum += arr[i]
    return sum

시간 복잡도: O(n), 여기서 n은 구간의 길이

2. 누적 합 배열 방식

단순 반복문의 방식을 이용하면 구간 합을 많이 구해야할때 시간복잡도가 O(nm), (여기서 m은 쿼리 개수)만큼 증가한다

이를 방지하기 위해 미리 누적 합 배열을 만들어 해결한다

예시

다음과 같은 배열이 있다

인덱스 0 1 2 3 4 5
값 2 5 1 4 3 6

이에 대한 모든 누적 합을 구해준다