알고리즘 - 12. 세그먼트 트리
세그먼트 트리를 사용해야 할 때
세그먼트 트리는 배열에 대해 구간 쿼리와 점 업데이트를 효율적으로 수행해야 할 때 사용합니다. 가장 일반적으로 구간 합 쿼리에 사용되지만, 다음과 같이 응용할 수 있습니다:
- 구간 합 쿼리 (고전적인 사용 사례)
- 구간 최소값/최대값 쿼리 (RMQ)
- 구간 GCD/LCM 쿼리 수학적 연산용
- 조건을 만족하는 원소의 개수 구간 내에서
- 구간 업데이트 연산 (지연 전파 사용)
- 작은 구간을 결합하여 계산할 수 있는 모든 결합 연산 (XOR, AND, OR, 곱셈)
예제 문제
실시간 거래 대시보드: 수천 명의 동시 사용자가 있는 100만 개의 주식 [s₀, s₁, ..., s₉₉₉,₉₉₉]을 추적하는 실시간 거래 시스템을 구축하고 있습니다. 매초 시스템은 다음을 처리해야 합니다:
- 10,000개 이상의 구간 쿼리: "234,567부터 456,789까지 주식의 총 가치는?"
- 5,000개 이상의 가격 업데이트: "주식 345,678의 가격이 $120에서 $125로 변경되었습니다"
- 둘 다 지속적이고 동시에 발생
누적 합 배열이 실패하는 이유:
- 누적 합 배열은 O(1) 쿼리를 제공하지만 각 업데이트에 O(n)이 필요합니다
- n = 1,000,000이고 초당 5,000번의 업데이트 = 초당 50억 연산! 💥
- 시스템이 부하를 견디지 못합니다
세그먼트 트리를 사용하면:
- 구축: O(n) 일회성 설정
- 각 쿼리: O(log n) ≈ 20연산
- 각 업데이트: O(log n) ≈ 20연산
- 총 부하: (10,000 × 20) + (5,000 × 20) = 초당 300,000연산 ✓
핵심: 빈번한 업데이트와 대량 데이터에 대한 빈번한 쿼리가 있을 때, 세그먼트 트리의 두 연산 모두에 대한 O(log n)이 필수적입니다.
세그먼트 트리가 실제로 하는 일
세그먼트 트리는 배열 세그먼트에 대한 정보를 저장하는 이진 트리입니다. 각 노드는 구간을 나타내며 그 구간에 대한 연산(합계 등)의 결과를 저장합니다.
회사 부서를 조직하는 것처럼 생각하세요:
- 루트 노드: "회사 전체의 총 예산은?"
- 내부 노드: "이 부서의 총 예산은?"
- 리프 노드: "이 특정 팀의 예산은?"
연산 작동 방식
BUILD 연산 - "세그먼트를 계층적으로 조직"
배열 [100, 200, 150, 80]에서 세그먼트 트리를 구축할 때:
- 각 원소에 대한 리프 노드 생성 (구간 [0,0], [1,1] 등을 나타냄)
- 각 부모는 자식들의 합을 저장
- 루트는 전체 배열의 합을 포함
- 트리 구조로 효율적인 구간 쿼리가 가능해집니다
[530] <- [0,3]의 합
/ \
[300] [230] <- [0,1]과 [2,3]의 합
/ \ / \
[100] [200] [150] [80] <- 개별 원소
0 1 2 3 <- 배열 인덱스QUERY 연산 - "임의 구간의 합 가져오기"
구간 [1, 3]을 쿼리할 때:
- 루트에서 시작하여 현재 구간이 쿼리 구간과 겹치는지 확인
- 완전히 포함되는 경우: 저장된 합을 반환
- 부분적으로 겹치는 경우: 양쪽 자식을 재귀적으로 확인
- 겹치는 세그먼트의 결과를 결합
UPDATE 연산 - "값을 변경하고 모든 합 유지"
인덱스 2를 180으로 업데이트할 때:
- 인덱스 2의 리프 노드를 업데이트
- 모든 조상 노드를 재귀적으로 업데이트
- 영향을 받는 각 노드가 합을 재계산
- 모든 구간 합이 자동으로 정확하게 유지됩니다
이러한 연산이 발생하는 시점
이러한 연산은 필요에 따라 명시적으로 호출됩니다:
const segTree = SegmentTree.build([100, 200, 150, 80], 0, 3);
// QUERY: 인덱스 1부터 3까지 주식의 합 가져오기
let portfolioValue = segTree.rangeQuery(1, 3); // 430 반환
// UPDATE: 인덱스 2의 주식이 180으로 증가
segTree.update(2, 180);
// QUERY: 업데이트 후 새로운 합 가져오기
portfolioValue = segTree.rangeQuery(1, 3); // 460 반환세그먼트 트리의 아름다움은 한 번 구축되면 구간 크기에 관계없이 쿼리와 업데이트 모두 O(log n) 시간이 걸린다는 것입니다!
가장 중요한 통찰
모든 구간은 트리에 저장된 O(log n)개의 겹치지 않는 세그먼트로 분해될 수 있습니다 - 구간을 재귀적으로 반으로 나눔으로써, 임의의 구간 쿼리가 최대 O(log n)개의 노드를 방문하는 트리를 만들어 쿼리와 업데이트 모두에서 로그 시간을 달성합니다.
기억할 점: 알고리즘의 천재성은 특정 "2의 거듭제곱 같은" 세그먼트에 대한 결과를 미리 계산하는 데 있습니다. 각 레벨에서 결정해야 하는 것은: "이 세그먼트가 완전히 내부에, 완전히 외부에, 아니면 부분적으로 쿼리 구간과 겹치는가?"라는 간단한 판단입니다. 각 노드에서의 이 간단한 결정이 임의의 구간 쿼리에 효율적으로 답하기 위해 올바른 세그먼트를 자동으로 결합합니다.
결정 프레임워크
세그먼트 트리에는 세 가지 주요 결정이 있습니다:
구축 시 (분할 정복):
- 구간을 재귀적으로 반으로 분할
- 상향식으로 노드 생성
- 부모를 위해 자식의 값 결합
쿼리 시 (구간 겹침 확인):
- 겹침 없음: 이 서브트리 전체를 건너뜀
- 완전한 겹침: 이 노드의 값을 직접 반환
- 부분적 겹침: 양쪽 자식을 쿼리하고 결합
업데이트 시 (변경 전파):
- 리프 노드 업데이트
- 부모를 자식의 합으로 재계산
- 루트까지 전파
코드
class SegmentTree {
constructor(segmentSum, leftBoundary, rightBoundary) {
// 이 노드가 저장하는 것
this.sum = segmentSum;
// 이 노드가 나타내는 구간 [leftBoundary, rightBoundary] 양쪽 포함
this.leftBoundary = leftBoundary;
this.rightBoundary = rightBoundary;
// 트리 구조
this.leftChild = null;
this.rightChild = null;
}
// BUILD: 배열에서 트리 생성 - O(n) 시간
static build(array, startIndex, endIndex) {
const isSingleElement = startIndex === endIndex;
// DECISION FRAMEWORK: 기저 사례 - 단일 원소에 대한 리프 노드
if (isSingleElement) {
const elementValue = array[startIndex];
return new SegmentTree(elementValue, startIndex, endIndex);
}
// DECISION FRAMEWORK: 구간을 반으로 나눔
const midpoint = Math.floor((startIndex + endIndex) / 2);
const leftHalfEnd = midpoint;
const rightHalfStart = midpoint + 1;
// 양쪽 절반을 재귀적으로 구축
const leftSubtree = SegmentTree.build(array, startIndex, leftHalfEnd);
const rightSubtree = SegmentTree.build(array, rightHalfStart, endIndex);
// DECISION FRAMEWORK: 결합 - 부모는 자식의 합을 저장
const combinedSum = leftSubtree.sum + rightSubtree.sum;
const parentNode = new SegmentTree(combinedSum, startIndex, endIndex);
// 트리 구조 연결
parentNode.leftChild = leftSubtree;
parentNode.rightChild = rightSubtree;
return parentNode;
}
// UPDATE: array[targetIndex]를 newValue로 변경 - O(log n) 시간
update(targetIndex, newValue) {
// 경계 확인 - 인덱스는 이 노드의 구간 내에 있어야 함
const indexOutOfBounds = targetIndex < this.leftBoundary ||
targetIndex > this.rightBoundary;
if (indexOutOfBounds) {
// 인덱스가 이 서브트리에 속하지 않음 - 업데이트 불필요
return;
}
const isLeafNode = this.leftBoundary === this.rightBoundary;
const leafContainsTarget = isLeafNode &&
(this.leftBoundary === targetIndex);
// DECISION FRAMEWORK: 대상 리프를 찾음
if (leafContainsTarget) {
this.sum = newValue;
return;
}
// DECISION FRAMEWORK: 어느 자식이 targetIndex를 포함하는가?
const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
const targetIsInRightHalf = targetIndex > midpoint;
if (targetIsInRightHalf) {
this.rightChild.update(targetIndex, newValue);
} else {
this.leftChild.update(targetIndex, newValue);
}
// DECISION FRAMEWORK: 변경사항을 위로 전파
const updatedLeftSum = this.leftChild.sum;
const updatedRightSum = this.rightChild.sum;
this.sum = updatedLeftSum + updatedRightSum;
}
// QUERY: 구간 [queryStart, queryEnd]의 합 가져오기 - O(log n) 시간
rangeQuery(queryStart, queryEnd) {
// 경계 확인 - 이 노드의 구간과 겹침 없음
const noOverlap = queryEnd < this.leftBoundary ||
queryStart > this.rightBoundary;
if (noOverlap) {
// 쿼리 구간이 이 서브트리와 전혀 겹치지 않음
return 0;
}
// 쿼리 구간이 이 노드의 구간과 어떻게 관련되는지 확인
const exactMatch =
queryStart === this.leftBoundary && queryEnd === this.rightBoundary;
// DECISION FRAMEWORK: 완전한 겹침 - 미리 계산된 합 사용
if (exactMatch) {
return this.sum;
}
// 이 노드 구간의 분할점 찾기
const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
const leftHalfEnd = midpoint;
const rightHalfStart = midpoint + 1;
// DECISION FRAMEWORK: 자식과의 겹침 결정
const queryIsEntirelyInRightHalf = queryStart >= rightHalfStart;
const queryIsEntirelyInLeftHalf = queryEnd <= leftHalfEnd;
if (queryIsEntirelyInRightHalf) {
// 쿼리는 오른쪽 서브트리만 필요
return this.rightChild.rangeQuery(queryStart, queryEnd);
}
if (queryIsEntirelyInLeftHalf) {
// 쿼리는 왼쪽 서브트리만 필요
return this.leftChild.rangeQuery(queryStart, queryEnd);
}
// DECISION FRAMEWORK: 쿼리가 양쪽 자식에 걸침 - 분할하고 결합
const leftPortion = this.leftChild.rangeQuery(queryStart, leftHalfEnd);
const rightPortion = this.rightChild.rangeQuery(rightHalfStart, queryEnd);
const totalSum = leftPortion + rightPortion;
return totalSum;
}
}
// === 사용 예제: 실시간 거래 시스템 ===
// 시연용으로 8개 주식의 작은 버전 시뮬레이션
const stockPrices = [100, 200, 150, 80, 250, 300, 175, 220];
// 세그먼트 트리 구축 - O(n) 일회성 비용
console.log("거래 시스템을 위한 세그먼트 트리 구축 중...");
const tradingSystem = SegmentTree.build(stockPrices, 0, 7);
// 동시에 발생하는 빠른 쿼리와 업데이트 시뮬레이션
console.log("\n=== 고빈도 거래 활동 시뮬레이션 ===");
// 다른 사용자로부터의 여러 구간 쿼리
console.log("\n사용자 쿼리 (동시 발생):");
console.log(`트레이더 A - 포트폴리오 [2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 805
console.log(`트레이더 B - 포트폴리오 [0-3]: $${tradingSystem.rangeQuery(0, 3)}`); // 530
console.log(`트레이더 C - 포트폴리오 [4-7]: $${tradingSystem.rangeQuery(4, 7)}`); // 945
// 실시간으로 발생하는 시장 업데이트
console.log("\n시장 업데이트: 주식 3이 $80에서 $120으로 급등");
tradingSystem.update(3, 120);
// 새로운 쿼리가 즉시 변경사항 반영
console.log("\n시장 변경 후 쿼리 (즉시 반영):");
console.log(`트레이더 A - 포트폴리오 [2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 845
console.log(`트레이더 D - 포트폴리오 [1-4]: $${tradingSystem.rangeQuery(1, 4)}`); // 690
// 또 다른 빠른 업데이트
console.log("\n시장 업데이트: 주식 5가 $300에서 $250으로 하락");
tradingSystem.update(5, 250);
// 더 많은 동시 쿼리
console.log("\n추가 사용자 쿼리:");
console.log(
`트레이더 E - 전체 포트폴리오 [0-7]: $${tradingSystem.rangeQuery(0, 7)}`
); // 1545
console.log(
`트레이더 F - 고가 주식 [4-7]: $${tradingSystem.rangeQuery(4, 7)}`
); // 895
// 아름다움: 이 모든 연산이 각각 O(log n) 시간에 수행되었습니다!
// 실제 환경에서 n = 1,000,000일 때도 쿼리/업데이트당 약 20번의 연산만 필요합니다의문 해소
흔한 의문 #1: "트리가 [0,1]이나 [2,3]같은 세그먼트로 나뉜다면, [0,2]는 어떻게 쿼리하나요? 정확히 그 구간을 저장하는 노드가 없잖아요!"
왜 이것이 불가능해 보이는가
트리 구조를 보면 이렇게 생각할 수 있습니다:
[0,3]
/ \
[0,1] [2,3]
/ \ / \
[0] [1] [2] [3][0,2]를 나타내는 단일 노드가 없습니다. 그렇다면 어떻게 쿼리할 수 있을까요?
핵심 통찰: 여러 노드 결합하기
모든 가능한 구간에 대해 단일 노드가 필요하지 않습니다! 세그먼트 트리는 여러 노드의 결과를 결합합니다:
// 쿼리 [0,2]는 다음과 같이 분해됩니다:
query(0, 2) = query(0, 1) + query(2, 2)
= node[0,1].sum + node[2].sum
= 300 + 150 = 450알고리즘이 쿼리 [0,2]를 처리하는 방법은 다음과 같습니다:
- 루트 [0,3]에서 시작 - 쿼리 구간 [0,2]가 부분적으로 겹침
- 중간점(1)에서 쿼리 분할:
- 왼쪽 자식 [0,1]: 쿼리 [0,1] - 완전한 겹침, 합 반환
- 오른쪽 자식 [2,3]: 쿼리 [2,2] - 부분적 겹침, 더 깊이 들어감
- [2,3]에서 다시 분할:
- 왼쪽 자식 [2]: 쿼리 [2,2] - 완전한 겹침, 합 반환
- 결합: [0,1]의 합 + [2]의 합 = 답!
쿼리 [0,2]의 시각적 분해:
쿼리 [0,2]:
[0,3] "쿼리 분할"
/ \
[0,1]✓ [2,3] "부분적"
/ \
[2]✓ [3]✗
반환: [0,1].sum + [2].sum마법: 임의의 구간 [L,R]은 트리에 이미 저장된 최대 O(log n)개의 겹치지 않는 세그먼트로 분해될 수 있습니다. 레벨당 2개 이상의 노드가 필요하지 않으므로, 8원소 트리에서 [1,6]과 같은 쿼리도 최대 2×log₂(8) = 6개의 노드만 접근합니다.
흔한 의문 #2: "왜 누적 합 배열을 사용하지 않나요? prefixSum[i] = 0부터 i까지 원소의 합을 유지하면 prefixSum[R] - prefixSum[L-1]로 O(1) 시간에 임의의 구간 쿼리에 답할 수 있습니다."
왜 누적 합이 더 나아 보일 수 있는가
누적 합 배열은 구간 쿼리에 우수해 보입니다:
// 누적 합 접근법
prefixSums = [0, 100, 300, 450, 530, 780, 1080];
// 쿼리 [2,5] = prefixSums[6] - prefixSums[2] = 1080 - 300 = 780
// O(1) 쿼리 시간 - O(log n)보다 나아 보입니다!이것은 절대적으로 사실입니다...값을 업데이트할 필요가 없다면. 누적 합 접근법은 빈번한 쿼리가 있는 정적 배열에 완벽합니다.
왜 누적 합이 업데이트로 무너지는가
여기서 문제가 발생합니다:
// 인덱스 2를 150에서 180으로 업데이트
// 이제 인덱스 2 이후의 모든 누적 합을 업데이트해야 합니다:
prefixSums[3] = 480 (450이었음)
prefixSums[4] = 560 (530이었음)
prefixSums[5] = 810 (780이었음)
prefixSums[6] = 1110 (1080이었음)
// 이것은 업데이트마다 O(n) 시간이 걸립니다!빈번한 업데이트가 있으면 누적 합은 병목이 됩니다. m번의 업데이트와 q번의 쿼리가 있는 경우:
- 누적 합: 업데이트당 O(n) × m번의 업데이트 = O(m·n) 합계
- 세그먼트 트리: 업데이트당 O(log n) × m번의 업데이트 = O(m·log n) 합계
핵심 트레이드오프
누적 합을 사용할 때:
- 배열이 정적 (업데이트 없음) 또는 업데이트가 드묾
- O(1) 쿼리 시간이 필요
- 예: 과거 데이터의 누적 통계 계산
세그먼트 트리를 사용할 때:
- 쿼리와 업데이트 모두 빈번
- 두 연산 모두에 O(log n)으로 충분
- 예: 실시간 포트폴리오 값을 표시하는 라이브 대시보드
효율성 차이를 보여주는 구체적 예
100만 개의 주식이 있는 거래 시스템을 고려합니다 (n = 1,000,000):
시나리오: 초당 10,000번의 쿼리와 10,000번의 업데이트
누적 합의 경우:
- 각 업데이트: O(n) = 1,000,000 연산
- 10,000번의 업데이트 = 초당 100억 연산
- 시스템 충돌! 💥
세그먼트 트리의 경우:
- 각 업데이트: O(log n) = 약 20 연산
- 10,000번의 업데이트 = 초당 200,000 연산
- 각 쿼리: O(log n) = 약 20 연산
- 10,000번의 쿼리 = 초당 200,000 연산
- 합계: 초당 400,000 연산 - 완전히 관리 가능! ✓
왜 세그먼트 트리의 구조가 빠른 업데이트를 가능하게 하는가
마법은 업데이트 전파 방식에 있습니다:
세그먼트 트리에서 인덱스 2를 업데이트하려면:
[1110] <- 이것만 업데이트
/ \
[250] [860] <- 이것만 업데이트
/ \ / \
[100] [150] [180] [80] <- 이것만 업데이트
↑
변경된 값
O(log n)개의 노드만 업데이트가 필요 - 트리 레벨당 하나씩!이를 모든 후속 합을 업데이트해야 하는 누적 합과 비교하세요. 트리 구조는 임의의 업데이트의 "피해 범위"를 리프에서 루트까지의 경로로만 제한합니다.
결론
세그먼트 트리는 약간 느린 쿼리 (O(log n) 대 O(1))를 극적으로 빠른 업데이트 (O(log n) 대 O(n))와 맞바꿉니다. 데이터가 자주 변경될 때 이 트레이드오프는 필수적입니다. 두 연산 모두에 대한 로그 보장으로 세그먼트 트리는 동적 구간 쿼리 문제의 최우선 선택이 됩니다.