Sparse Table이란?주어진 배열의 구간 정보를 미리 전처리하여, 특정 구간에 대한 쿼리를 매우 빠르게 처리할 수 있는 자료구조. 전처리 시간 복잡도 : O(NlogN)쿼리 응답 시간 복잡도 : O(logN) 또는 O(1) (min, max, GCD 같은 멱등 함수의 경우)Sparse Table의 핵심 조건적용하려는 연산(함수)은 결합법칙(Associativity) 을 만족해야 한다.예: min(a, b, c) = min(min(a, b), c)예: gcd(a, b, c) = gcd(gcd(a, b), c)중간에 배열이 변경되지 않아야 한다. (Immutable)중간에 값이 바뀌면 그 때 마다 테이블을 다시 전처리해야 한다. Sparse Table이 효율적으로 동작하는 이유는 모든 양의 정수는 2의..