세그먼트 트리 (segment - tree)
세그먼트 트리는 해당 포스트에 설명이 잘 돼있다.
출처: http://isukorea.com/blog/home/waylight3/216
세그먼트 트리(Segment Tree) / 인덱스 트리(Index Tree) :: 강의/IT/알고리즘 :: ISU 블로그
void update_range(int node, int begin, int end, int left, int right, int diff) { update_lazy(node, begin, end); if (end < left || right < begin) return; if (left <= begin && begin <= right) { tree[node] += (end - begin + 1) * diff; i
isukorea.com
세그먼트 트리를 이해하기 위해 확실히 알아둬야 할 내용은 배열 arr와 tree 의 관계이다.
예를들어 arr값을 2,3,7,4,5,9,6,1 이렇게 8개의 값을 저장하기 위해서는 세그먼트 트리로는 총 15개의 노드가 필요하다. tree의 사이즈와 이 8개의 값이 어떤 상관관계가 있냐면 먼저 1개의 값을 트리에 표현하기 위해서는 트리 높이가 1이면 되고 2개를 표현하기 위해서는 트리 높이가 2, 3~4개를 표현하기 트리높이가 3이 돼야 한다. 즉 트리의 높이 h= (올림(logn)) 이 되고 트리의 사이즈는 2^(h+1) 로 해야 포화 이진트리를 표현할 수 있으며 인덱스를 0이 아닌 1부터 지정했을 때 마지막 인덱스까지 런타임에러 없이 삽입을 할 수 있다.
이렇게 단말노드에 arr의 값을 놓고 부모노드는 자식노드의 합을 표현하는 것이 segment tree이다. 이 세그먼트 트리를 이용하면 구간합이나 여러 쿼리문을 logn의 수행만으로 해결할 수 있게된다.
세그먼트 트리 문제
백준:
2042 구간 합 구하기 https://www.acmicpc.net/problem/2042
소스코드
2243 사탕상자 https://www.acmicpc.net/problem/2243
사탕상자같은 경우의 쿼리문에서 주의할 점은 찾고자하는 idx를 비교와 연산을 통해 쭉쭉 들어가다가 최종 단말노드 도착점에 도착하고나면 return을 해주는데 그 이후에도 idx의 값은 계속해서 작아지게 돼서 반드시 처음에 한번만 찾고 나머지 재귀함수로 들어가려고 할때
if (idx>0&&(node * 2 <= tree_size && tree[node * 2] >= idx) ) query(tree, node * 2, start, mid, idx);
와 같이 idx 조건을 추가하여 처음 값 출력 후 동작이 되지 않게 막아줘야 한다.
소스코드
1275 커피숍 2 https://www.acmicpc.net/problem/1275
소스코드