목록2025/02/07 (1)

개발 일기

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

Segment Tree 초기화 Segment Tree 구간 합 구하기 Segment Tree 값 업데이트 (기존 값과 바꿀 값의 차를 통한 업데이트) diff를 활용한 update방식보다 해당 코드가 더 직관적인듯  시간 복잡도트리 초기화 (init)세그먼트 트리는 완전 이진 트리로, 전체 노드 개수는 O(2N) (약 4N)init 함수는 한 번의 호출당 O(1), 전체적으로 O(N)시간 복잡도: O(N)구간 합 조회 (sum)이진 트리의 높이는 O(log N)sum 함수는 트리를 따라 내려가며 분할 정복, 최악의 경우 O(log N) 개의 노드를 방문시간 복잡도: O(log N)값 업데이트 (update)특정 위치의 값을 변경하면, 관련된 모든 부모 노드를 업데이트해야 함update 함수는 이진 트리..
Back-End/Java 2025. 2. 7. 14:11
이전 Prev 1 Next 다음