Segment tree beats (세그 비츠)

4년 전 코포 블로그 글로 올라온 자료구조로, 언젠가부터 웰노운이 된 듯하다. segment tree with lazy propogation을 확장한 형태로, $O(NlogN)$ 혹은 $O(Nlog^2N)$ 정도의 시간복잡도를 가진다.

 

아이디어

일반적인 레이지 세그트리는 아래와 같이 구현한다.

void updseg(int idx, int l, int r, int x, int y, int z) {
  if (r < x || y < l) return;
  if (x <= l && r <= y) {
      puttag(idx, z);
      return;
  }
  propagate(idx);
  int m = (l + r) / 2;
  updseg(idx * 2, l, m, x, y, z);
  updseg(idx * 2 + 1, m + 1, r, x, y, z);
  update(idx);
}

 

이를 일반화하면 아래와 같이 쓸 수 있다.

void updseg(int idx, int l, int r, int x, int y, int z) {
  if (break_condition()) return;
  if (tag_condition()) {
      puttag(idx, z);
      return;
  }
  propagate(idx);
  int m = (l + r) / 2;
  updseg(idx * 2, l, m, x, y, z);
  updseg(idx * 2 + 1, m + 1, r, x, y, z);
  update(idx);
}

일반적인 레이지 세그의 경우에는 break_condition이 r < x || y < l, tag_condition이 x <= l && r <= y인 것이다. 

break_condition과 tag_condition을 잘 설정하면, 보다 이상한 복잡한 문제들을 해결할 수 있다. 시간복잡도를 계산하는 것은 좀 어렵긴 하지만...

 

예시

이제 세그 비츠를 이용하여 풀 수 있는 문제들을 살펴보겠다.

Min update query

1. $i \in [l, r]$에 대해, $A_i \leftarrow min(A_i, x)$

2. $i \in [l, r]$에 대해 $A_i \leftarrow A_i + x$

3. $i \in [l, r]$에 대해 $A_i$의 합

 

세그트리의 노드에서 들어야 하는 값은 sum, mx, mx2, mxcnt이다. mx와 mx2는 각각 구간의 최댓값과 2번째로 큰 값을 의미하며, mxcnt는 최댓값의 개수를 의미한다.

break_condition은 r < x || y < l || mx <= x이며, tag_condition은 x <= l && r <= y && mx2 <= x이다. mx2 <= x < mx이라는 것은 최댓값에만 갱신이 일어난다는 것이다.

시간복잡도는 $O(Nlog^2N)$으로, 위에서 언급한 코포 블로그 글에 설명되어있다. 

 

Divide query

1. $i \in [l, r]$에 대해, $A_i \leftarrow \lfloor \frac{A_i}{d} \rfloor$

2. $i \in [l, r]$에 대해 $A_i \leftarrow A_i + x$

3. $i \in [l, r]$에 대해 $A_i$의 합

 

이 문제 역시 수들 사이의 간격이 점차 줄어든다는 특징이 있다. 따라서 이에 착안하여 mx와 mn를 구하자. mx == mn인 경우에는 2번 쿼리와 같아진다. mx == mn + 1인 경우에는 1번 쿼리 이후 mx == mn가 되거나, mx == mn + 1이 유지된다. 전자의 경우는 각 노드마다 최대 1번만 일어나고, 후자의 경우에는 1번 쿼리와 같이 처리하면 된다.

 

Historical information

$B_i$는 $A_i$의 historical max이다. i.e. 매 쿼리가 시행될 때마다 $B_i \leftarrow max(B_i, A_i)$

1. $i \in [l, r]$에 대해 $A_i \leftarrow A_i + x$

2. $i \in [l, r]$에 대해 $A_i \leftarrow max(A_i - x, 0)$

3. $i \in [l, r]$에 대해 $A_i \leftarrow x$

4. $A_i$의 구간합

5. $B_i$의 구간합

 

max query는 위에서 설명한 min query와 같은 방식으로 해결할 수 있다. $B_i$를 구하기 위해서는 $D_i=B_i - A_i$를 정의하자. 그러면 $A_i \leftarrow A_i + x$ 연산이 일어날 때 $D_i \leftarrow max(D_i - x, 0)$이 된다. 이는 $B_i$에 대한 max query이므로 해결할 수 있다.

 

 

 

백준의 수열과 쿼리 19번, 25번, 26번, 28번, 29번을 세그 비츠로 해결할 수 있다.