일반적인 결합법칙이 성립하는 이항연산에 대해 sparse table은 공간 복잡도가 O(n log n)이고 초기화가 O(n log n), 쿼리가 O(log n), 업데이트가 O(n)이 됩니다.

그러나 멱등법칙과 교환법칙이 추가로 성립하면 쿼리를 O(1)에 할 수 있게 됩니다.

segment tree는 결합법칙이 성립하는 이항연산에 대해 공간 복잡도가 O(n), 초기화 O(n), 쿼리 및 업데이트가 O(log n)입니다.

따라서 멱등법칙이 성립하는 최솟값, 최댓값에 대해서는 sparse table을 썼을 때 쿼리를 O(1)에 할 수 있다는 장점이 있지만 그 외의 경우는 별 이점이 없고 무엇보다 업데이트가 필요한 경우 사실상 사용할 수 없습니다.

sparse Table은 update 쿼리를 효율적으로 처리 못합니다. update가 있을 경우 sparse table을 쓰면 안돼요.

어떤 cell을 바꿨을 때, 같이 바꿔야 하는 cell의 개수가 O(n)이에요.

첫 번째 row에서 1개, 두 번째 row에서 2개, 3번째에서 4개 4번째에서 8개..., 이렇게 바뀝니다. (마지막 row는 예외적으로 좀 적게 바뀌죠).

시간 초과가 나는 이유는 이것 때문이에요.

1. Segment Tree가 Sparse Table과 비교해서 얻는 시간/공간적 우위가 존재하는지

대부분의 경우에 segment tree가 좋습니다.

sparse table의 경우 연산하는 구간이 겹쳐도 (되는지/안 되는지)에 따라 구간 쿼리를 (O(1)/O(logn))에 처리할 수 있는데,

O(logn)의 경우 똑같이 쿼리에 O(logn)이 들지만 공간 복잡도랑 build하는 시간 복잡도 둘 다 O(n)인 segment tree가 좋고

O(1)인 경우에도 쿼리 개수가 엄청 많은 게 아니라면 제 경험상 build하는 시간이 적게 드는 segment tree쪽이 웬만하면 빨랐습니다. (큰 차이는 없습니다. 세그: n + qlogn, 스파스: nlogn + q)

2. 모든 Segment Tree 문제는 시간/공간의 중대한 비효율 없이 Sparse Table로 상호 변환이 가능한지

update가 없다면 sparse table로 풀어도 중대한 비효율이 생기진 않으나, 이런 문제는 많지 않고 앞서 말씀 드린 것처럼 웬만하면 segment tree가 좋습니다.

그냥 segment tree는 사기입니다. segment tree 쓰세요. PS계의 벌쳐에요.

저는 연산 구간이 겹치도 되는 쿼리(대표적으로 range minimum query)를 O(1)에 처리할 때랑 binary lifting(lca 구할 때 )을 사용할 때만 sparse table을 사용합니다. 사실 별로 안 써요...

solved에서 "tag:sparse_table -tag:segtree"로 검색해서 제가 푼 문제들 지금 살펴봤는데 여기서 sparse table로 푼 것은 반도 안되네요.

다들 너무 좋은 답변 감사합니다....!