PS/자료구조
세그먼트 트리 (Segment Tree)
Segment Tree란? Segment Tree(구간 트리)는 각 구간을 이진 트리로 관리하여 원소의 변경 혹은 구간의 연산을 효율적으로 처리할 수 있는 자료구조 입니다. 먼저 Segment Tree가 대표적으로 어떻게 활용되는 지 알아보겠습니다. 아래 문제를 해결해봅시다. 길이가 \(N\)인 배열 \(A\)가 주어지고, 아래의 쿼리를 효율적으로 처리해야 됩니다. 1. \([l, r]\) 구간의 합 구하기 2. \(i\)번째 수를 \(x\)로 변경하기 Naive하게 접근하면 \(1\)번 쿼리는 \(O(N)\), \(2\)번 쿼리는 \(O(1)\)에 처리할 수 있습니다. 하지만 Segment Tree는 \(1\), \(2\)번 쿼리 모두를 \(O(logN)\)에 처리할 수 있습니다. 아이디어 Segmen..