구간 합(Range Sum) 문제란?
구간 합 문제는 배열의 특정 구간에 속한 원소들의 합을 구하는 문제입니다. 가장 간단한 방법은 매번 구간의 합을 직접 계산하는 것이지만, 이 경우 시간 복잡도가 O(N)이 되어 쿼리가 많아질수록 비효율적입니다.
누적/접두사 합 (Prefix Sum)
- 누적 합은 미리 각 인덱스까지의 누적 합을 계산하여 배열(P)에 저장하는 기법입니다.
- 계산:
P[i] = P[i-1] + A[i] - 구간 합 쿼리:
i부터j까지의 합은P[j] - P[i-1]로O(1)만에 계산할 수 있습니다. - 단점: 배열의 특정 원소 값이 변경(갱신) 되면, 이후의 모든 누적 합을 다시 계산해야 하므로
O(N)의 시간이 걸립니다.
데이터 갱신이 잦은 경우: 세그먼트 트리
- 세그먼트 트리(Segment Tree) 는 구간 합과 데이터 갱신을 모두 효율적으로 처리할 수 있는 자료구조입니다.
- 구간 합 쿼리:
O(log N) - 데이터 갱신:
O(log N)
따라서, 데이터의 갱신이 빈번하게 일어나는 구간 합 문제에서는 세그먼트 트리를 사용하는 것이 훨씬 효율적입니다.