728x90 세그먼트 트리1 세그먼트 트리란? 세그먼트 트리(Segment Tree)란? 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등)을 구하는 데 사용하는 자료구조이다. 트리 종류 중에 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. (O(logN)) 아래 예제를 통해 세그먼트 트리(Segment Tree)를 왜 사용하는지 알아보자. (Ex) 위와 같은 배열이 있다고 하자. 이 때 데이터의 개수는 10개로 인덱스는 0부터 9까지 차례대로 1~10의 원소가 삽입되어 있다. 만약 인덱스 2부터 8까지 데이터를 더하려면 어떻게 할까? 위 그림처럼 2~8 범위의 원소를 하나씩 다 더하면 된다. 결과는 42이다. 이러한 방식으로 다른 특정 구간의 합을 구한다고 고려했을 때 앞에서 하나씩 .. 2023. 3. 29. 이전 1 다음 728x90
