[자료구조] 세그먼트 트리

세그먼트 트리로 구간합* 구하기

• 선형적으로 구간합을 구하면 O(N)의 시간 복잡도를 가지므로 비효율적임
• 트리구조를 이용하여 구간합을 구하여 O(logN)의 시간복잡도로 구간합을 구함

 

*구간합 : 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 구하는 것

 

이미지 출처 : Wikipedia

 

1. 완전 이진 트리에 데이터 삽입
2. 구간 합 트리 생성(특정 범위 인덱스의 값을 저장함)
3. 필요한 구간에 포함된 트리 노드의 값들로 구간합을 계산함

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수