Dynamic Segment Tree

Prerequisite

• Segment Tree

Dynamic Segment Tree

$N \le 1,000,000$ 정도일 때, 구간합을 구하거나 특정 자리의 값을 업데이트 한다고 하자.

그럼 세그먼트 트리를 써서 구현을 하는것이 국룰이다.

그런데, $N\le 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,\,\infty]$ 구간을 관리하면서 모든 인덱스에 $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을 끼얹는 문제이다. 연습용으로 풀어보면 좋다. 구현이 꽤나 어려울 것이다.