문제 설명
문제: 일정 범위의 합 구하기
n개의 정수가 담긴 배열 arr가 주어질 때,
다음 쿼리들을 처리하는 함수를 작성하시오:
- 1.
update(index, value): 배열arr의index번째 값을value로 갱신합니다. - 2.
rangeSum(left, right): 배열arr의left번째부터right번째(0-indexing)까지의 합을 계산합니다.
주어진 배열과 쿼리들을 사용하여 update와 rangeSum의 요구 사항을 효율적으로 처리하세요.
배열의 크기는 최대 10^5이고, 쿼리의 개수는 최대 10^5입니다.
해결 방법
이 문제는 범위 합을 효율적으로 구하고 업데이트를 처리해야 하므로, 세그먼트 트리를 사용할 수 있습니다.
세그먼트 트리는 주어진 배열을 구간(구간 합 쿼리) 단위로 나누어 저장하는 이진트리 기반의 자료구조입니다.
세그먼트 트리의 정의
세그먼트 트리는 다음과 같은 속성을 가집니다:
- 각 노드는 하나의 배열 구간에 대한 정보를 저장합니다. 이 정보는 구간의 합 혹은 최소, 최대 등으로 설정할 수 있습니다.
- 트리의 높이는
O(log n)이며, 이는 쿼리 연산과 업데이트 연산 모두에 대해O(log n)의 시간이 소요됨을 의미합니다.
세그먼트 트리 구현 단계
세그먼트 트리를 구현하기 위해 다음과 같은 절차를 따릅니다:
- 초기화: 주어진 배열을 기반으로 세그먼트 트리를 초기화합니다.
- 구간 합 쿼리: 특정 구간의 합을 계산하기 위해 필요한 레벨의 노드들을 재귀적으로 가져옵니다.
- 업데이트: 특정 인덱스의 값을 업데이트하고 관련 세그먼트 노드들을 갱신합니다.
JavaScript 코드 구현
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(this.n * 4);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
// 리프 노드에 정수 값 저장
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
// 왼쪽 자식 정의
this.build(arr, node * 2 + 1, start, mid);
// 오른쪽 자식 정의
this.build(arr, node * 2 + 2, mid + 1, end);
// 부모 노드는 두 자식의 합으로 정의
this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
}
}
rangeSum(left, right) {
return this.sum(0, 0, this.n - 1, left, right);
}
sum(node, start, end, left, right) {
if (right < start || end < left) {
// 요청된 범위와 겹치지 않으면 0 반환
return 0;
}
if (left <= start && end <= right) {
// 요청된 범위가 구간 안에 포함되면 노드 반환
return this.tree[node];
}
const mid = Math.floor((start + end) / 2);
const leftSum = this.sum(node * 2 + 1, start, mid, left, right);
const rightSum = this.sum(node * 2 + 2, mid + 1, end, left, right);
return leftSum + rightSum;
}
update(index, value) {
this.updateValue(0, 0, this.n - 1, index, value);
}
updateValue(node, start, end, index, value) {
if (start === end) {
// 리프 노드 업데이트
this.tree[node] = value;
} else {
const mid = Math.floor((start + end) / 2);
if (index <= mid) {
this.updateValue(node * 2 + 1, start, mid, index, value);
} else {
this.updateValue(node * 2 + 2, mid + 1, end, index, value);
}
// 부모 노드 업데이트
this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
}
}
}
// 사용 예시
const arr = [1, 3, 5, 7, 9, 11];
const segmentTree = new SegmentTree(arr);
console.log(segmentTree.rangeSum(1, 3)); // 15
segmentTree.update(1, 10);
console.log(segmentTree.rangeSum(1, 3)); // 22
결론
세그먼트 트리는 배열의 구간 합을 효율적으로 처리할 수 있는 강력한 도구입니다.
이 자료구조를 통해 O(log n)의 시간복잡도로 알림 처리 및 구간 합 계산이 가능합니다.
실전에서의 복잡한 문제들이 요구할 때, 세그먼트 트리를 활용하여 많은 이점을 얻을 수 있습니다.
추가 연습 문제
다음 문제들을 연습해 보세요:
- 세그먼트 트리를 사용하여 주어진 배열의 최소값 구하기
- 구간에서 특정 값을 더하는 쿼리 추가
- 세그먼트 트리로 최대값 구하기