[문제해결기법] 6. 세그먼트 트리
1. Segment Tree 부분합 문제에서 응용 가능 생성 코드 2. 합을 구하는 코드 [start, end]의 합을 구하려면 루트부터 시작하여 다음을 점검한다. 노드가 나타내는 구간이 [left, right]라면 다음의 4가지 경우가 가능하다. 각 경우마다 처리는 다음과 같다. (1) [start, end]와 [left, right]가 겹치지 않음 -> 할 일이 없다 (2) [start, end]가 [left, right]를 포함 -> 미리 구해둔 [left, right]의 합을 사용한다. (3) [start, end]를 [left, right]가 포함 -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다. (4) [start, end]가 [left, right..
2023. 4. 18.
