세그먼트 트리 (segment - tree)

세그먼트 트리는 해당 포스트에 설명이 잘 돼있다.

출처: http://isukorea.com/blog/home/waylight3/216

세그먼트 트리(Segment Tree) / 인덱스 트리(Index Tree) :: 강의/IT/알고리즘 :: ISU 블로그

세그먼트 트리를 이해하기 위해 확실히 알아둬야 할 내용은 배열 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

소스코드