때로는 문제를 풀기 위해 자료구조에 완전한 영속성이 필요하지는 않지만, 어떻게든 이전 상태로 되돌아갈 수는 있어야 합니다.
이 글에서는 몇 가지 일반적인 접근 방법과 그 대표적인 활용 사례를 살펴보겠습니다.
#쿼리에 대한 제곱근 휴리스틱
표준적인 문제를 하나 살펴봅시다: 크기가 $n$인 배열이 있고, 구간 덧셈 쿼리와 구간 합 쿼리를 $q$개 수행해야 합니다. (세그먼트 트리와 그 밖의 트리들의 존재는 잠시 잊읍시다.)
업데이트 쿼리가 없다면 이 문제는 단순히 누적 합 배열로 해결할 수 있습니다:
int s[maxn]; // [0, r)
s[0] = 0
for (int i = 0; i < n; i++)
s[i+1] = s[i] + a[i];
원래 문제로 돌아갑시다. 모든 변경 쿼리를 크기가 대략 $\sqrt q$인 블록으로 나누고, $\sqrt q$개의 쿼리마다 이전의 모든 쿼리를 반영한 누적 합 배열을 $O(n)$에 정직하게 새로 구축하겠습니다.
이제 각 합 쿼리에 답하기 위해 직전 체크포인트의 누적 합에 대한 쿼리에 $O(1)$의 시간을 쓰고, 아직 반영되지 않은 모든 쿼리를 단순히 선형으로 훑으며 「보정」하는 데 $O(\sqrt q)$의 시간을 더 쓰면 됩니다.
const int c = 300; // ~= sqrt(q)
struct query { int l, r, x; };
vector<query> buffer; // запросы, не учтенные в префиксных суммах
int sum(int l, int r) {
int res = s[r + 1] - s[l];
for (query q : buffer)
// пересечем запрос суммы со всеми запросами
res += q.x * max(0, min(r, q.r) - max(l, q.l));
return res;
}
void rebuild() {
vector<int> d(n, 0); // массив дельт
for (query q : buffer) {
d[q.l] += x;
d[q.r + 1] -= x;
}
buffer.clear();
int delta = 0, running_sum = 0;
for (int i = 1; i <= n; i++) {
p[i] += running_sum;
delta += d[i];
running_sum += delta;
}
}
void upd(int l, int r, int x) {
buffer.push_back({l, r, x});
if (buffer.size() == c)
// буфер слишком большой; надо пересчитать префиксные суммы и очистить его
rebuild();
}
이러한 풀이는 $O(n \sqrt q + q \sqrt q)$ 시간에 동작합니다. $\sqrt q$개의 쿼리마다 누적 합을 $O(n)$ 시간에 다시 구성하고, 각 합 쿼리마다 이전 쿼리 $O(\sqrt q)$개를 살펴보기 때문입니다.
#정적 구조를 동적 구조로 바꾸기
앞의 방법은 누적 합 배열뿐만 아니라 모든 정적 자료 구조에 적용할 수 있습니다.
문제. 볼록 껍질에 점을 추가하고 접선을 찾아야 합니다(즉, 내적 $a_i x + b_i y$를 최대화하는 점을 찾아야 합니다).
또한 $\sqrt n$개의 쿼리마다 볼록 껍질을 다시 구성하고, 접선 쿼리에 답할 때에는 구성된 볼록 껍질에서 얻은 후보 외에 버퍼에 있는 점들과의 스칼라곱 $\sqrt n$개를 추가로 고려할 수 있습니다.
선형 시간에 껍질을 다시 구성할 수 있도록 점들의 정렬된 리스트를 유지한다면, 이 방법은 $O(n \cdot (\sqrt n + \log n) + \sqrt n \cdot n) = O(n \sqrt n)$에 동작합니다.
문제. 미리 알려진 순서대로 볼록 껍질에 점을 추가하고 볼록 껍질에서 점을 삭제하면서 접선을 찾아야 합니다.
이것은 조금 더 복잡합니다. 쿼리를 명시적으로 블록으로 나누고, 각 블록을 따로 처리합시다. 각 블록마다 그 블록 전체에 걸쳐 존재하는 점들만으로 볼록 껍질을 만들고 나머지 쿼리는 버퍼에 저장합니다 — 이러한 점들을 찾으려면 $O(\sqrt n)$개의 쿼리를 미리 살펴보고 삭제된 간선을 어떤 배열이나 해시 테이블에 표시해야 합니다.
그러면 접선 쿼리에 답할 때, 구축된 껍질에서 얻은 후보 외에도 해당 쿼리 시점에 존재하는 모든 점을 함께 고려합니다. 이러한 점들은 현재 블록의 기록을 분석하여 마찬가지로 $O(\sqrt n)$에 모두 찾을 수 있습니다.
#2의 거듭제곱 크기의 구조
문제에 삭제 연산이 없거나 어떤 방식으로든 삭제를 흉내 낼 수 있다면, 비슷하지만 더 강력한 기법을 적용할 수 있는 경우가 많습니다. 바로 크기가 2의 거듭제곱인 구조(예를 들어 볼록 껍질)를 $O(\log n)$개 유지하되, 크기가 같은 구조가 두 개 존재하지 않도록 하는 것입니다.
이를 위해서는 새로운 점을 추가할 때 다음과 같이 해야 합니다
- 새 점에 대해 그 점 하나만 들어 있는 크기 1의 새 구조를 만들고;
- 그다음, 크기가 1인 구조가 이미 존재한다면 그것을 새 구조와 합쳐 크기가 2인 구조를 만듭니다;
- 그다음, 크기 2인 구조가 이미 존재하면 그것을 새 구조와 합쳐 크기 4인 구조를 만듭니다
…이와 같은 과정을, 해당 크기의 구조가 존재하지 않는 2의 거듭제곱을 찾을 때까지 계속합니다.
전체 원소 수 $n$에 의해 이 합집합에 어떤 크기의 구조가 존재할지가 유일하게 결정됩니다. 그 구조들은 $n$의 이진 표현에서 1인 자리에 대응하므로, 기본 구조는 항상 $O(\log n)$개 이하입니다.
볼록 껍질의 경우, 정렬된 점 배열들을 병합하면 각 구조를 그 크기에 비례하는 시간에 만들 수 있습니다. 크기 1인 구조는 매 연산마다 만들고, 크기 2인 구조는 2번의 연산마다 만들며, 크기 4인 구조는 4번의 연산마다 만드는 식으로 계속합니다. 이러한 정적 구조들의 합집합을 유지하는 데에는 분할 상환으로 $O(n \log n)$번의 연산이 듭니다. 각 크기마다 $O(n)$씩입니다.
질의에 대해서는 질의를 $O(\log n)$개의 기본 구조 모두에 전달하고 그 답을 합쳐서 답하겠습니다. 볼록 껍질의 경우 이는 총 $O(\log^2 n)$의 시간이 걸립니다.
볼록 껍질과 포락선 외에도, 이러한 접근 방식은 예를 들어 문자열 오토마타를 갱신하거나 검색용 인덱스를 동적으로 구축하는 데에도 유용합니다.