Prerequisite
Dynamic Segment Tree
N≤1,000,000 정도일 때, 구간합을 구하거나 특정 자리의 값을 업데이트 한다고 하자.
그럼 세그먼트 트리를 써서 구현을 하는것이 국룰이다.
그런데, N≤1,000,000,000 이라고 해보자. 그럴때도 쓸 수 있을까?
바로 다이나믹 세그먼트 트리를 이용하면 된다.
구간이 넓어봤자 업데이트하거나 구간합을 구하는 쿼리 Q는 문제에서 그렇게 크게 주어지지 않을 것이기 때문에 충분히 구할 수 있다.
결론부터 말하자면 다이나믹 세그먼트 트리도 일반 세그먼트 트리와 동일한 공간복잡도와 시간복잡도를 갖는다.
물론 구간이 증가할수록 트리의 depth는 깊어지기 때문에 더 메모리가 많이 들고, 느리고, 어떤 구현 방식을 사용하느냐에 따라도 조금씩 달라서 메모리가 넉넉할 때만 사용할 수 있다.
원리
일반적인 세그먼트 트리는 [1,N] 의 구간에 대해서 정적으로 배열을 선언해두고, 보통 1번 노드를 루트로 하고 대략 노드가 2N 개가 있다.
그런데, 다이나믹 세그먼트 트리는 이렇게 동작하지 않는다.
노드를 그때 그때 필요할 때 마다 만들어내서 관리를 한다.
다이나믹 세그먼트 트리도 일단 관리하려는 구간에 대해서 정해두긴 해야한다.
구현 1 - 포인터 이용
포인터를 이용해서 구현하는건 직관적이라는 장점이 있다.
다음과 같은 코드를 보자.
struct node {
int value = 0;
node *l = 0, *r = 0;
};
struct dynamic_seg_tree {
node *root = new node();
void update(node *n, int nl, int nr, int i, int v) {
if (i < nl || i > nr) return;
if (nl == nr) {
n->value = v;
return;
}
int m = nl + (nr - nl) / 2;
if (i <= m) {
if (!n->l) n->l = new node();
update(n->l, nl, m, i, v);
} else {
if (!n->r) n->r = new node();
update(n->r, m + 1, nr, i, v);
}
n->value = (n->l ? n->l->value : 0) + (n->r ? n->r->value : 0);
}
int query(node *n, int nl, int nr, int l, int r) {
if (!n || nr < l || nl > r) return 0;
if (nl >= l && nr <= r) return n->value;
int m = nl + (nr - nl) / 2;
return query(n->l, nl, m, l, r) + query(n->r, m + 1, nr, l, r);
}
};
node 라는 구조체를 정의해 구간의 합을 의미하는 value와 각각 왼쪽 오른쪽 자식 포인터를 갖게 한다.update에서는 일반 세그먼트 트리와 유사한데, i 가 실제로 가 있어야 할 구간쪽에만 자식이 없다면 할당해주는 식으로 파고들어가서 최대한 메모리를 절약한다.query에서는 현재 노드가 정의되지 않은 구간이라면 이 구간에는 업데이트가 된 적이 없다는 뜻이므로 바로 0을 반환할 수 있다.
사용하기
BOJ 2042 - 구간 합 구하기 문제를 패보도록 하자.
우린 [0,∞] 구간을 관리하면서 모든 인덱스에 5를 곱해서 쿼리를 날리는 정상적이지 않은 짓(?)을 할 것이다.
바로 다음과 같이 코드를 짜도 문제를 풀 수 있다!
const int MAX = numeric_limits<long long>::max();
void solve() {
int n, m, k;
cin >> n >> m >> k;
dynamic_seg_tree seg;
for (int i = 0; i < n; i++) {
int v;
cin >> v;
seg.update(seg.root, 0, MAX, i * 5, v);
}
for (int _ = 0; _ < m + k; _++) {
int a, b, c;
cin >> a >> b >> c;
if (a == 1) {
b--;
seg.update(seg.root, 0, MAX, b * 5, c);
} else {
b--, c--;
cout << seg.query(seg.root, 0, MAX, b * 5, c * 5) << endl;
}
}
}
구현 2 - 배열 이용
배열을 이용해서 짜는 것도 구조는 매우 비슷한데, NULL 포인터 대신 −1같은 값을 가리키게 해두는 것이다.
처음에 배열의 크기를 예상해서 미리 할당해두거나, push_back 으로 크기를 하나하나 늘려줄 수 있다.
웬만하면 미리 할당해두는 방식이 좀 더 빠르다.
실제 코드를 보도록 하자.
struct node {
int value = 0, l = -1, r = -1;
};
struct dynamic_seg_tree {
int nxt = 2;
vector<node> tree = vector<node>(3000000);
void update(int n, int nl, int nr, int i, int v) {
if (i < nl || i > nr) return;
if (nl == nr) {
tree[n].value = v;
return;
}
int m = nl + (nr - nl) / 2;
if (i <= m) {
if (tree[n].l == -1) tree[n].l = nxt++;
update(tree[n].l, nl, m, i, v);
} else {
if (tree[n].r == -1) tree[n].r = nxt++;
update(tree[n].r, m + 1, nr, i, v);
}
tree[n].value =
(~tree[n].l ? tree[tree[n].l].value : 0) +
(~tree[n].r ? tree[tree[n].r].value : 0);
}
int query(int n, int nl, int nr, int l, int r) {
if (n == -1 || nr < l || nl > r) return 0;
if (nl >= l && nr <= r) return tree[n].value;
int m = nl + (nr - nl) / 2;
return query(tree[n].l, nl, m, l, r) + query(tree[n].r, m + 1, nr, l, r);
}
};
연습 문제
BOJ 20212 - 나무는 쿼리를 싫어해~
이 문제는 다이나믹 세그먼트 트리에 Lazy Propagation을 끼얹는 문제이다. 연습용으로 풀어보면 좋다. 구현이 꽤나 어려울 것이다.
Comments