일반적인 트립은 각 원소가 어떤 키를 가지는 집합을 위한 자료구조입니다. 이 키들은 집합 위에 순서를 정하며, 트립에 대한 모든 쿼리는 보통 어떤 식으로든 이 순서와 연관되어 있습니다.
하지만 이 순서를 자명하지 않은 방식으로 바꾸는 쿼리가 있다면 어떻게 해야 합니까? 예를 들어, 다음과 같은 연산을 수행할 수 있어야 하는 배열이 있다면
- 임의의 구간의 합을 출력하고,
- 임의의 구간을 «뒤집기», 즉 나머지 원소는 바꾸지 않고 $l$부터 $r$까지의 원소를 역순으로 재배치하기.
두 번째 연산이 없었다면 단순히 원소의 인덱스를 키로 사용했겠지만, 뒤집기 연산이 있으면 인덱스를 빠르게 최신 상태로 유지할 방법이 없습니다.
해결책은 다음과 같습니다. 키를 버리고, 그 대신 필요할 때 키를 암묵적으로 복원할 수 있게 해 주는 정보를 유지합시다. 구체적으로, 각 정점과 함께 그 서브트리의 크기를 저장합시다:
struct Node {
int prior, size = 1;
// ^ размер поддерева
// ...
};
그러면 키(원소의 위치)는 그 원소보다 왼쪽에 있는 원소의 개수로 복원할 수 있으며, 이 값은 트리를 따라 내려가는 동안 다시 계산할 수 있습니다.
서브트리의 크기는 합과 마찬가지 방식으로 유지하겠습니다. 즉, 정점에 구조적 변경이 일어날 때마다 호출할 보조 함수를 작성합니다.
int size(Node *v) { return v ? v->size : 0; }
void upd(Node *v) { v->size = 1 + size(v->l) + size(v->r); }
merge 연산은 어디에서도 키를 사용하지 않으므로 바뀌지 않지만, split에서는 루트의 키 대신 루트의 위치를 사용해야 합니다. 이제 split은 “처음 k개의 원소를 잘라 내라"로 생각하는 편이 더 편리합니다:
pair<Node*, Node*> split(Node *p, int k) {
if (!p) return {0, 0};
if (size(p->l) + 1 <= k) {
auto [l, r] = split(p->r, k - size(p->l) - 1);
// ^ правый сын не знает количество вершин слева от него
p->r = l;
upd(p);
return {p, r};
}
else {
auto [l, r] = split(p->l, k);
p->l = r;
upd(p);
return {l, p};
}
}
이것으로 끝입니다. 이제 우리에게는 키에 의존하지 않고 원하는 대로 자를 수 있는 멋지고 유연한 자료구조가 생겼습니다.
#예시: ctrl+x, ctrl+v
Node* ctrlx(int l, int r) {
auto [T, R] = split(root, r);
auto [L, M] = split(T, l);
root = merge(L, R);
return M;
}
void ctrlv(Node *v, int k) {
auto [l, r] = split(root, k);
root = merge(l, merge(v, r));
}
#예시: 뒤집기
원래 문제로 돌아갑시다. 임의의 부분 문자열을 뒤집는 쿼리를 $O(\log n)$에 처리해야 합니다. 즉, $a_l$의 값을 $a_r$와 바꾸고, $a_{l+1}$을 $a_{r-1}$과 바꾸는 식입니다.
각 정점에 해당 정점의 부분 구간이 뒤집혔음을 뜻하는 플래그 rev를 저장합시다:
struct Node {
bool rev;
// ...
};
세그먼트 트리의 지연 연산 기법과 비슷하게 처리합시다. 이러한 정점을 만날 때마다 그 자식들에 대한 링크를 서로 바꾸고, 자식들에게는 이 표시를 넘겨줍니다:
void push(node *v) {
if (v->rev) {
swap(v->l, v->r);
if (v->l)
v->l->rev ^= 1;
if (v->r)
v->r->rev ^= 1;
}
v->rev = 0;
}
마찬가지로, 이 함수를 merge와 split의 시작 부분에서 호출하겠습니다.
reverse 함수 자체는 다음과 같이 구현합니다. 필요한 구간을 잘라 내고 플래그를 바꿉니다.
void reverse(int l, int r) {
auto [T, R] = split(root, r);
auto [L, M] = split(T, l);
M->rev ^= 1;
root = merge(L, merge(M, R));
}