스파스 테이블

스파스 테이블을 소개한다. 다소 특수한 분야에서 사용되지만, 스파스 테이블은 구현이 간단하면서도 매우 강력한 기능을 제공한다.

문제 정의

다음과 같은 상황을 가정한다:

[*] 여기서 f는 "멱등성(idempotent)"을 가진다. 이 개념은 잠시 후에 설명한다.

우리의 과제는 다음과 같다:

예를 들어, 숫자 배열이 다음과 같고:

var a = [ 20, 3, -1, 101, 14, 29, 5, 61, 99 ]

함수 f가 min 함수인 경우를 생각해 보자.

그리고 구간 [3, 8)에 대한 쿼리가 주어졌다면, 우리는 다음 요소들을 살펴본다:

101, 14, 29, 5, 61

이 요소들은 배열 a에서 인덱스 [3, 8) 범위에 해당하는 요소들이다. 즉, 인덱스 3부터 8 이전까지의 요소들이다. 이 숫자들을 모두 min 함수에 전달하면 최솟값을 구할 수 있다. 이 쿼리의 답은 5이다. 왜냐하면 min(101, 14, 29, 5, 61)의 결과가 5이기 때문이다.

이제 수백만 개의 쿼리를 처리해야 한다고 상상해 보자.

그리고 배열의 크기도 매우 크다고 가정하자. 여기서 Q = 1000000이고 N = 500000이다. 두 숫자 모두 매우 크다. 각 쿼리에 빠르게 답할 수 있어야 한다. 그렇지 않으면 쿼리의 수가 우리를 압도할 것이다!

이것이 우리가 해결해야 할 문제다.

이 문제에 대한 단순한 해결책은 각 쿼리에 대해 for 루프를 사용해 답을 계산하는 것이다. 그러나 Q와 N이 매우 크면 이 방법은 너무 느리다. Sparse Table이라는 데이터 구조를 사용하면 쿼리에 대한 답을 더 빠르게 계산할 수 있다. 지금까지의 문제는 세그먼트 트리와 완전히 동일하다. (세그먼트 트리를 알고 있다고 가정한다.) 그러나! 세그먼트 트리와 Sparse Table 사이에는 한 가지 중요한 차이점이 있다. 그것은 바로 우리가 선택한 함수 f와 관련이 있다.

작지만 중요한 문제 ... 멱등성(Idempotency)

[A, D) 구간의 답을 찾고 싶다고 가정해 보자. 그리고 이미 **[A, B)**와 [C, D) 두 구간의 답을 알고 있다. 중요한 점은 이 두 구간이 겹친다는 것이다! 즉, C < B이다.

겹치는 구간

그렇다면 어떤 의미가 있을까? f가 최솟값 함수라면, **[A, B)**와 **[C, D)**의 답을 결합할 수 있다. 단순히 두 답의 최솟값을 취하면 된다: result = min(x1, x2). 이렇게 하면 [A, D) 구간의 최솟값을 쉽게 구할 수 있다. 구간이 겹치더라도 올바른 최솟값을 찾을 수 있다.

하지만 이제 f가 덧셈 연산 +라고 가정해 보자. 이제는 구간의 합을 구하는 상황이다. 같은 방법을 적용하면 잘못된 결과가 나온다. **[A, B)**와 **[C, D)**의 답을 더하면 [A, D) 구간의 답이 틀리게 된다. 왜냐하면 겹치는 부분의 요소를 두 번 계산하기 때문이다.

나중에 보겠지만, Sparse Table은 쿼리에 답하기 위해 이와 동일한 기법을 사용한다. 위에서 설명한 방식대로 답을 결합한다. 하지만 이 방법은 +, *, XOR 등과 같은 특정 이항 연산자를 사용할 수 없다. 이 연산자들은 이 기법과 호환되지 않기 때문이다.

Sparse Table의 최고 속도를 얻기 위해서는 사용하는 f가 **멱등성**을 가진 이항 연산자여야 한다. 수학적으로 말하면, 모든 가능한 x에 대해 f(x, x) = x를 만족하는 연산자를 의미한다. 실제로 이 조건을 만족하는 연산자만이 겹치는 구간의 답을 결합할 수 있다. 멱등성을 가진 f의 예로는 min, max, gcd, boolean AND, boolean OR, bitwise AND, bitwise OR 등이 있다.

Segment Tree의 경우 f가 멱등성을 가질 필요가 없다는 점이 Sparse Table과의 중요한 차이점이다.

이제 이 문제를 해결했으니 본격적으로 시작해 보자!

스파스 테이블의 구조

f를 최솟값 함수로 설정하고 다음과 같은 배열을 사용한다:

var a = [ 10, 6, 5, -7, 9, -8, 2, 4, 20 ]

이 경우, 스파스 테이블은 다음과 같이 구성된다:

스파스 테이블

여기서 무슨 일이 일어나고 있을까? 다양한 구간이 보인다.
맞다! 스파스 테이블은 수많은 쿼리 [l, r)에 대한 답을 미리 저장해둔다.
핵심 아이디어는 Q개의 쿼리를 처리하기 전에, 스파스 테이블 table을 미리 채워두는 것이다.
이렇게 하면 일종의 캐시처럼 동작한다. 쿼리에 답할 때, 쿼리를 더 작은 "하위 쿼리"로 나눌 수 있다.
각 하위 쿼리에 대한 답은 이미 캐시에 저장되어 있다.
table에서 하위 쿼리에 대한 캐시된 답을 상수 시간에 조회하고,
이를 결합해 원래 쿼리에 대한 전체 답을 빠르게 얻을 수 있다.

문제는 가능한 모든 쿼리에 대한 답을 저장할 수 없다는 점이다.
그렇게 하면 테이블이 너무 커진다! 결국 스파스 테이블은 스파스해야 한다.
그렇다면 어떻게 해야 할까?
"가장 좋은" 구간만 선택해 답을 저장한다.
그리고 "가장 좋은" 구간은 너비가 2의 거듭제곱인 구간이다!

예를 들어, 쿼리 [10, 18)에 대한 답은 테이블에 저장된다.
왜냐하면 구간의 너비: 18 - 10 = 8 = 2**3이 2의 거듭제곱이기 때문이다 (**는 지수 연산자이다).
마찬가지로, [15, 31)에 대한 답도 테이블에 저장된다.
너비: 31 - 15 = 16 = 2**4가 다시 2의 거듭제곱이기 때문이다.
반면, [1, 6)에 대한 답은 테이블에 없다.
구간의 너비: 6 - 1 = 5가 2의 거듭제곱이 아니기 때문이다.
결과적으로, 배열 a 안에 들어가는 모든 가능한 구간에 대한 답을 저장하지 않는다.
너비가 2의 거듭제곱인 구간만 저장한다.
이 방법은 구간이 a 내에서 어디에서 시작하든 상관없이 적용된다.
이 접근 방식이 효과적이며, 상대적으로 매우 적은 공간을 사용한다는 점을 점차 확인할 수 있다.

스파스 테이블은 table[w][l]이 [l, l + 2**w)에 대한 답을 포함하는 테이블이다.
table[w][l]의 항목은 다음과 같다:

예시:

스파스 테이블

스파스 테이블은 2차원 배열을 사용해 구현할 수 있다.

public class SparseTable<T> {
  private var table: [[T]]

  public init(array: [T], function: @escaping (T, T) -> T, defaultT: T) {
      table = [[T]](repeating: [T](repeating: defaultT, count: N), count: W)
  }
  // ...    
}

스파스 테이블 구축

스파스 테이블을 구축할 때, 각 테이블 엔트리를 왼쪽 아래에서 시작해 오른쪽 위로 이동하며 계산한다. (다이어그램을 참고한다.) 먼저 w = 0일 때 모든 구간을 계산한 다음, w = 1일 때 모든 구간을 계산한다. 이 과정을 w가 충분히 커져 구간이 배열의 절반 이상을 커버할 때까지 반복한다. 각 w에 대해 l = 0, 1, 2, 3, ... 순서로 구간을 계산하며 N에 도달할 때까지 진행한다. 이 모든 과정은 이중 for-in 루프를 사용해 달성한다:

for w in 0..<W {
  for l in 0..<N {
    // table[w][l] 계산
  }
}

table[w][l]을 계산하는 방법은 다음과 같다:

스파스 테이블

예를 들어, a = [ 10, 6, 5, -7, 9, -8, 2, 4, 20 ]이고 f가 min인 경우:

스파스 테이블

public init(array: [T], function: @escaping (T, T) -> T, defaultT: T) {
 let N = array.count
 let W = Int(ceil(log2(Double(N))))
 table = [[T]](repeating: [T](repeating: defaultT, count: N), count: W)
 self.function = function
 self.defaultT = defaultT

 for w in 0..<W {
   for l in 0..<N {
     if w == 0 {
       table[w][l] = array[l]
     } else {
       let first = self.table[w - 1][l]
       let secondIndex = l + (1 << (w - 1))
       let second = ((0..<N).contains(secondIndex)) ? table[w - 1][secondIndex] : defaultT
       table[w][l] = function(first, second)
     }
   }
 }
}

스파스 테이블을 구축하는 데는 O(NlogN) 시간이 소요된다. 테이블 자체는 **O(NlgN)**의 추가 공간을 사용한다.

쿼리에 대한 답변 찾기

이제 스파스 테이블을 구축했다고 가정하자. 이제 Q개의 쿼리를 처리할 차례다. 여기서 우리의 노력이 빛을 발한다.

f = min이고 다음과 같은 배열이 있다고 하자:

var a = [ 10, 6, 5, -7, 9, -8, 2, 4, 20 ]

그리고 [3, 9) 범위의 쿼리가 있다.

  1. 먼저 [3, 9) 범위에 들어가는 가장 큰 2의 거듭제곱을 찾는다. 이 구간의 너비는 9 - 3 = 6이다. 따라서 이 범위에 들어가는 가장 큰 2의 거듭제곱은 4이다.

  2. 너비가 4인 두 개의 새로운 쿼리 [3, 7)와 [5, 9)를 만든다. 이 두 쿼리는 원래 구간 전체를 완전히 덮도록 배치한다.
    스파스 테이블

  3. 이 두 구간의 너비가 정확히 2의 거듭제곱이므로, 스파스 테이블에서 w = 2에 해당하는 항목을 사용해 답을 찾을 수 있다. [3, 7)의 답은 table[2][3]으로 주어지고, [5, 9)의 답은 table[2][5]로 주어진다.
    이제 min(table[2][3], table[2][5])를 계산하고 반환한다. 이것이 최종 답이다! 🎉. 두 구간이 겹치더라도 문제가 되지 않는다. 왜냐하면 처음 선택한 f = min이 멱등성을 가지기 때문이다.

일반적으로 각 쿼리 [l, r)에 대해...

  1. 구간 안에 들어가는 가장 큰 2의 거듭제곱 너비를 찾아 W를 구한다. 이때 가장 큰 너비는 2**W이다.

  2. 너비가 2**W인 두 개의 하위 쿼리를 만들고, 이들이 전체 구간을 완전히 덮도록 배치한다. 구간이 빠지지 않도록 하려면 한쪽은 왼쪽에 맞추고 다른 한쪽은 오른쪽에 맞춰야 한다.
    스파스 테이블

  3. f(table[W][l], table[W][r - 2**W])를 계산하고 반환한다.

    public func query(from l: Int, until r: Int) -> T {
  let width = r - l
  let W = Int(floor(log2(Double(width))))
  let lo = table[W][l]
  let hi = table[W][r - (1 << W)]
  return function(lo, hi)
}

쿼리에 대한 답을 찾는 데 걸리는 시간은 **O(1)**이다.

희소 테이블 분석

세그먼트 트리와의 비교

[†] 기술적으로는 query 메서드를 수정해 idempotent가 아닌 함수를 지원하도록 할 수 있다. 하지만 이렇게 하면 시간이 O(1)에서 O(lgn)으로 증가해 스파스 테이블의 원래 목적인 빠른 쿼리 지원이 무의미해진다. 이런 경우에는 세그먼트 트리(또는 펜윅 트리)를 사용하는 것이 더 나은 선택이다.

요약

여기까지입니다! Sparse Table을 활용한 더 많은 예제를 확인하려면 플레이그라운드를 참고하세요. 최솟값, 최댓값, 최대공약수, 불리언 연산자, 논리 연산자 등 다양한 예제를 확인할 수 있습니다.

함께 보기

Swift Algorithm Club을 위해 James Lawson이 작성함