목록2022/10 (1)
yoongrammer
세그먼트 트리(Segment Tree) 개념 및 구현
목차 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. 다음 예를 보겠습니다. A = {1, 2, 3, 4, 5 … ,N} 라는 배열에 아래 연산을 M번 수행한다고 생각해봅시다. 배열의 범위 합을 구하는 Query 연산 A[0] + A[1] + A[2] + … + A[N-1] i번째 배열 값을 v로 변경하는 Update 연산 A[i] = v 단순한 방법으로는 각각 배열에 접근하여 연산을 한다면 시간 복잡도는 1번 연산 O(N), 2번 연산 O(1)이 됩니다. 이 두 연산을 M번 수행한다면 총 시간 복잡도는 O(MN)+O(M) = O(MN)이 됩니다. 세그먼트 트리를 사용하면 범위 최소/최대 및 합계 Query 및..
자료구조 (Data structure)
2022. 10. 9. 16:32