희소 배열 (Sparse table)?앞서 구간에 대한 합계를 Prefix Sum을 이용해 계산을 했다면, 구간에 대해 최소값 또는 최대값을 계산하는 것은 조금 더 복잡한 문제입니다. Sparse table 을 이용하면 O(nlogn)의 전처리 이후 구간에 대한 최소값과 최대값을 구하는 것을 O(1) 시간복잡도로 수행할 수 있습니다. Sparse 라는 단어는 가능한 모든 구간을 저장하는 것이 아니라, 2의 거듭제곱 길이의 구간만 저장하기 때문에 붙여진 이름입니다. 모든 정수는 2의 거듭제곱을 한번씩 사용해서 표현할 수 있습니다. 당연하게도 모든 정수들은 이진수로 표현할 수 있고 7은 111, 9는 1001 이기 때문입니다. 예를 들면, 7은 4+2+1 이고 9는 8+1 과 같은 형태입니다. 이러한 원..