스파스 테이블 ( Sparse table )
Table of Contents 개요 1D sparse table 쿼리를 O(1)으로 처리하기 2D sparse table 문제 1. 개요 스파스 테이블은 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때 Function(Array[L], Array[L+1], ..., Array[R]) 계산을 빠르게 하기 위한 자료구조입니다. 간단하게 예를 들면, 'A[3] ~ A[7] 사이의 최소값을 구하라.'같은 식입니다. 여기에서 함수는 최소값 찾기, L = 3, R = 7이 되겠지요. 스파스 테이블은 아래의 두 조건이 성립할 때 사용할 수 있습니다. 조건 1) Array에 저장된 값이 변하지 않야야 한다. 조건 2) Function은 결합 법칙이 성립해야 한다. (즉, F(a,..
범위 쿼리 처리 ( Range Query )
2017. 11. 2. 20:26