[Algorithm] Segment Tree(세그먼트 트리)

Segment Tree 초기화

 

Segment Tree 구간 합 구하기

 

Segment Tree 값 업데이트 (기존 값과 바꿀 값의 차를 통한 업데이트)

 

diff를 활용한 update방식보다 해당 코드가 더 직관적인듯

 

 

시간 복잡도

1. 트리 초기화 (init)
   • 세그먼트 트리는 완전 이진 트리로, 전체 노드 개수는 O(2N) (약 4N)
   • init 함수는 한 번의 호출당 O(1), 전체적으로 O(N)
   • 시간 복잡도: O(N)
2. 구간 합 조회 (sum)
   • 이진 트리의 높이는 O(log N)
   • sum 함수는 트리를 따라 내려가며 분할 정복, 최악의 경우 O(log N) 개의 노드를 방문
   • 시간 복잡도: O(log N)
3. 값 업데이트 (update)
   • 특정 위치의 값을 변경하면, 관련된 모든 부모 노드를 업데이트해야 함
   • update 함수는 이진 트리를 따라 최대 O(log N) 개의 노드를 방문
   • 시간 복잡도: O(log N)

기존 구간 합(Prefix Sum)과 차이

→ 배열 값이 자주 변경된다면 Segment Tree가 압도적으로 유리 (O(log N)).
→ Prefix Sum은 변경이 거의 없는 환경에서만 적합.(Prefix Sum은 갑 변경 시 마다 O(N))