자료구조에서 '스파스 테이블(Sparse Table)'의 특징으로 올바른 것은?
어려움 freeCodeCamp해설
스파스 테이블은 배열의 각 위치에서 길이 2^k인 구간의 최솟값(또는 GCD)을 미리 계산하여 저장합니다. 이후 임의 구간 [l, r]의 최솟값을 두 개의 중첩 구간으로 덮어 O(1)에 응답합니다. 값 갱신이 불가능하여 정적 데이터에만 적합하며, 세그먼트 트리보다 쿼리가 빠릅니다.
스파스 테이블은 배열의 각 위치에서 길이 2^k인 구간의 최솟값(또는 GCD)을 미리 계산하여 저장합니다. 이후 임의 구간 [l, r]의 최솟값을 두 개의 중첩 구간으로 덮어 O(1)에 응답합니다. 값 갱신이 불가능하여 정적 데이터에만 적합하며, 세그먼트 트리보다 쿼리가 빠릅니다.
