Prerequisite

  • Segment Tree

0-1 Segment Tree

0-1 Segment Tree란 이름은 내가 지은 이름인데, 일반적인 세그먼트 트리에서 구간에 대해 합을 구할 수 있는것에 비해 이 세그먼트 트리는 전체 구간에서 0이 아닌 구간의 개수를 세준다.

보통 이 트리는 스위핑 알고리즘과 같이 쓰인다.

쿼리가 전체 구간에서만 가능하다.

이렇게 세그먼트 트리를 구성하면 구간이 몇번 중복되어 더해져 값이 1이상일 수 있지만, 1이상인 값들의 개수를 셀 때 쓸 수 있다.

image.png

빨간 구간에 1씩 더하는 연산을 했을 때, 우린 $[0,\,9]$에 쿼리를 날리면 1이상의 값이 있는 칸의 개수인 7을 얻고 싶은 것이다.

또한 이 자료구조는 구간에 대한 업데이트를 할 수 있다

시간복잡도는 $O(\log N)$ 이고, 전체 구간에 대한 쿼리에 대한 시간복잡도는 $O(1)$ 이다.

주의할 점

이 트리는 일반적인 세그먼트 트리와 동작 방식이 조금 다르기 때문에 절대적으로 주의해야 할 사항들이 있다.

전체 구간에 대해서만 쿼리가 가능하다.

즉, 세그먼트 트리의 크기를 $N$ 으로 잡았다면 항상 $0 \sim N-1$ 의 구간만 쿼리가 가능하다는 것이다.

이 쿼리는 $O(1)$에 가능하다.

동일한 구간에 대해서는 우선적으로 $+1$ 을 해야한다.

$[2,3]$ 에 $+1$ 업데이트를 했다면 추후에 더이상 트리가 필요없지 않는 이상 $[2,3]$ 에 $-1$ 업데이트가 되는 방식으로 트리를 사용해야 한다.

예를 들어, 구간의 길이가 $5$라면 $[0,4]$ 에 $+1$ 을 해준다음 $[3,3]$ 에 $-1$ 을 해주는 것 같은 쿼리를 날릴 수 없다.

왜인지 정확히 모르겠다. 사실 이 명제가 제대로 된건지도 모르겠고, 그냥 이걸 이용해 문제를 풀다가 왜안되지 하고 알아낸 사실이다. 아시는 분 제발 알려주세요
관련된 글을 코포 댓글 D 해설에서 찾을 수 있었다.

구현

구현은 세그먼트 트리와 크게 다르지 않다. 특히 쿼리는 아예 동일하게 날릴 수 있다.

$tree$ 라는 변수는 구간을 모두 변경시켜줘야 할 때만 더해준 $\sum$ 을, $len$ 이라는 변수는 $0{-}1$ 연산에 맞는 구간합을 가지고 있다고 하자.

이 글에서 1이상인 구간을 세는 연산을 $0{-}1$ 연산이라고 하겠다.

template<class T>  
struct seg_tree_01 {  
   int N;  
   vector<T> tree;  
   vi len;  
   seg_tree_01(int N) : N(N) {  
      int tree_size = 1 << ((int) ceil(log2(N)) + 1);  
      tree.resize(tree_size);  
      len.resize(tree_size);  
   }  
   void update(int n, int nl, int nr, int l, int r, T v) {  
      ???
   }  
   T query() { return len[1]; }  
   void update(int l, int r, T v) { update(1, 0, N - 1, l, r, v); }
};

쿼리부분에서 결국 반환해주는 값이 $len$ 이므로 쿼리에서 $0{-}1$ 연산의 결과를 반환함을 알 수 있다.

그럼 이제 update 부분만 어떻게 실행되면 되는지 생각해보자.

void update(int n, int nl, int nr, int l, int r, T v) {  
   if (nr < l || nl > r) return;  
   if (nl >= l && nr <= r) {  
      tree[n] += v;  
   } else {  
      int m = (nl + nr) >> 1;  
      update(n * 2, nl, m, l, r, v);  
      update(n * 2 + 1, m + 1, nr, l, r, v);  
   }  
   if (tree[n] > 0) len[n] = nr - nl + 1;  
   else if (nl == nr) len[n] = 0;  
   else len[n] = len[n * 2] + len[n * 2 + 1];  
}

일단 기본 구간합 세그먼트 트리처럼 $tree$ 에 대한 합을 계속해서 더해줘야한다.

그런데 특이하게도, 항상 $[nl,\,nr]$ 이 $[l,\,r]$ 구간에 완전히 포함될 때만 $tree$ 를 업데이트 시켜주고, 그 경우 자식의 트리를 업데이트 하지 않음을 알 수 있다.

이렇게 저장을 해야 $len$ 을 올바르게 업데이트시켜줄 수 있기 때문이다.

이제 $len$을 업데이트 하는과정을 보자.

  • $tree_n$ 에 값이 존재한다면 이 구간의 $0{-}1$ 값은 세그먼트 트리에서 정점이 의미하는 값 그 자체$(=nr-nl+1)$이다.
  • 만약 leaf 노드이고 $tree_n=0$ 이라면 $len_n=0$ 이다.
  • 그렇지 않다면 $len_n=len_{\rm left}+len_{\rm right}$ 이다.

왜 이것이 올바른지 조금 더 살펴보자.

image.png

$[0,\,3]$ 에 1씩 더해준다고 하자.

image.png

그럼 이렇게 $[0,~3]$ 노드에 $tree=1$ 이고 $len=3$ 으로 업데이트 된다. (루트 노드의 업데이트는 생략했다.)

그럼 이제 전체 구간에서 1이상인 칸의 개수는 $len_{root}$ 가 4로 업데이트가 되어 있을 것이므로 $4$ 라고 $O(1)$에 구해줄 수 있다.

좌표 압축

이 세그먼트 트리에서 유독 좌표압축까지 해야하는 문제들을 몇개 본거같은데, 좌표압축은 다음과 같이 한다.

$[l, r]$ 범위에 대한 어떤 것들을 존재하는 value 값으로 모아둘 때, $l, r$과 함께 $l-1$ 도 같이 모은다.

이제 $[l, r]$ 범위에 대한 업데이트에 대해 두 가지 경우가 나뉠 수 있다.

  1. 문제에서 다루는 좌표가 점을 의미해서 구간의 길이를 구하는 경우 (아래 7626 문제)
  2. 문제에서 다루는 좌표가 칸을 의미할 때 (아래 25447 문제)

$1$은 보통 $[l+1, r]$ 을 업데이트하고 트리 내부에서

len[n] = compressed[nr] - compressed[nl - 1]; 다음과 같이 코드만 다르게 쓴다.

이렇게하면 범위 $nl \sim nr$을 관장하는 노드 $n$이 정확히 그 구간을 의미하게 된다.

$2$는 보통 $[l, r]$ 을 업데이트하고 트리 내부에서

len[n] = compressed[nr] - compressed[nl - 1] 을 쓰자.

우린 $l-1$ 을 넣어두었기 때문에 이것이 동작한다.

연습 문제

BOJ 2185 - 직사각형의 합집합

image.png

이 문제는 0-1 세그먼트 트리를 이용해 풀어줄 수 있다.

일반성을 잃지않고 가로로 sweep하는 경우를 보자.

각각의 직사각형에 대해 $(x_1,y_1,y_2,z)$ 와 같은 event 객체를 두 개씩 만든다.

직사각형이 삽입될 때의 $z$는 $z=-1$, 제거될 때의 $z$ 는 $z=1$ 이다.

삽입될 때가 정렬순으로 더 빨리 오게 하기 위함이다.

이제 저 $x$ 에 대한 오름차순, $x$가 같다면 $z$에 대한 오름차순으로 정렬하고 스위핑한다.

이제 계속 vertical line들을 더해주고 빼주면서 그직전 값들과 차이를 계속해서 정답에 더해주면 된다.

  auto fn_x = [&](vector<array<int, 4>> event) -> int {
      sort(all(event), [&](auto &a, auto &b) {
         if (a[0] != b[0]) return a[0] < b[0];
         else return a[3] > b[3];
      });
      seg_tree_exist<int> seg(MX + 1);
      int ret = 0, prev = 0;
      for (auto &e: event) {
         seg.update(e[1], e[2], e[3]);
         int cur = seg.len[1];
         ret += abs(prev - cur);
         prev = cur;
      }
      debug(ret);
      return ret;
   };

BOJ 24272 - 루트 노드가 많은 트리일수록 좋은 트리이다

공식 해설 pdf

BOJ 7626 - 직사각형

좌표압축이다. 위 문제들과 비슷하게 푼다.

BOJ 25447 - Vinjete

DFS를 돌리며 이 세그먼트 트리를 써서 좌표압축까지 해서 풀어야 한다.

Comments