6549번 히스토그램에서 가장 큰 직사각형(세그먼트 트리, ceil) - ☆

#문제링크 :https://www.acmicpc.net/problem/6549

<전략>

1. 세그먼트 트리에 대한 이해가 필요하다. 블로그를 참고 했다.

2. 세그먼트 트리에 대한 이해를 하고서도 도무지 어떤 방법으로 풀어야 하는지 몰라서 같은 블로그의 답코드를 그대로 이해하고 따라 사용했다.

3. 세그먼트 트리는 완전 이진 트리인 경우가 많고, 리프 노드가 주어진 배열 각각의 원소 값을 가지게 되므로, 주어진 배열의 크기가 n이라 하면, n을 절반씩 계속 나누어 가면서 범위의 크기가 1이 될때까지 나누어 나간다. 따라서, 최대로 필요한 트리의 크기는 n보다 큰, 가장 작은 2의 거듭제곱에 2배만큼의 크기가 있으면 된다.

※주의사항

1. ceil은 올림함수로 cmath에 정의되어 있다.

2. log함수는 자연수(e)의 로그값이지만 log2와 같이 정수를 붙여주면 해당 수의 로그값을 취하고, double형으로 반환한다.

3. 세그먼트 트리에 대한 이해가 필요하다.

Code