누적된 변환과 lazy propagation 알고리즘

 안녕하세요. 2 ~ 3편에 걸쳐서, 레이지 프로퍼게이션을 적용한 세그먼트 트리를 쓰도록 하겠습니다. 세그먼트 트리에 쓰이는 lazy 기법을 1줄로 요약하면 아래와 같습니다.

 

 네. 앞으로 쓸 2 ~ 3편 글에 대한 핵심입니다. 이것만 정확하게 이해하시면 됩니다. 정말 중요한 키워드는 굵게 강조 표시까지 했는데요. 변환, 흡수, 전파. 이 셋입니다. 변환, 흡수, 전파? 이게 대체 무엇을 의미할까요? 이번 시간에는 이 중에 첫 번째 키워드와 두 번째 키워드인 변환과 흡수에 대해 알아보도록 하겠습니다.

 

 왜 자식에 전파하는지는 다음 포스트에서 이야기 해 보도록 하겠습니다.

 

---

 1번 변환을 생각해 봅시다.

 

 이 변환을 함수 f(v)로 표현해 봅시다. 그러면, f(v) = v + a가 됩니다. 다음에, 2번 변환을 생각해 봅시다.

 

 

 이 변환을 함수 g(v)로 표현해 봅시다. 그러면 g(v) = v + b가 됩니다. 그러면 어떠한 값 v'에 1번 변환을 수행하고, 2번 변환을 수행하면 어떻게 될까요?

 

 

 v'은 v'+(a+b)가 됩니다. 값 v'에다가 변환 f와 변환 g를 했더니, v'+(a+b)가 된 셈입니다. 그러면, f 변환과 g 변환을 누적한 변환 h(v') 는, v' + (a+b)로 봐도 되나요? 다시 말해서, 어떠한 값에 a를 더하는 변환과, 어떠한 값에 b를 더하는 변환을 누적시켰을 때, 어떠한 값에 a와 b를 더하는 변환이 됩니다.

 

 그러면, 이 누적된 변환을 어떻게 구간을 관리하는 노드에 넣을지 생각해 봅시다.

 

---

 먼저, 쿼리는 2종류만 있다고 생각해 봅시다.

 

 우리는 변환을 어떻게 잘 했으니, 누적된 변환을 어떻게 실제 구간 노드에 흡수할지 고민해 보아야 합니다. 이 상황을 그림으로 그려보겠습니다.

 

 누적된 변환, 혹은 누적된 쿼리가 q를 더한다. 라고 해 봅시다. 그리고 출력해야 하는 쿼리가 구간 합이라고 하면, 우리는 구간 노드의 대표값을, 구간에 들어있는 수들의 합이라고 하면 좋을 거에요. [node_s, node_e] 구간을 담당하는 대표값, 즉, node_s번째 위치부터, node_e번째 위치까지의 수들의 합이 v라고 해 봅시다.

 

 

 그러면, [node_s, node_e] 구간에 있는 수들 전체에 q를 더한다는 변환은 어떻게 해석하면 좋을까요? node_e - node_s + 1개의 노드에 q를 더하는 것이라고 해석할 수 있습니다. 예를 들어 구간의 길이가 2라고 해 봅시다.

 

 

 그러면 해당 노드에는, 원래 구간합이 v1 + v2였는데, v1 + v2 + 2q가 됩니다. 이것을 일반화 시키면, 노드가 관리하는 구간의 구간합이 v였고, 해당 노드에 q를 더하라는 쿼리가 들어왔습니다. 이 때, 우리는 q를 더하라는 변환을 노드에 반영해야 합니다. 그럴려면 해당 노드에 (node_e - node_s + 1)q를 더하면 됩니다.

 

 

 q를 더하라는 변환이 노드에 반영되었습니다. 이것을 '흡수되었다' 라고 합니다. 그렇게 되면, q를 더하라는 변환은 필요가 없습니다.

 

 

 그러면, 변환을 제거하면 됩니다. 잘 보면, 구간을 관리하는 자료구조 뿐만이 아니라, 변환을 관리하는 자료구조도 있어야 한다는 것을 알 수 있는데요. 이 둘 중에 후자는 lazy 배열로 관리합니다.

 

---

 이제 이런 문제를 생각해 봅시다.

 

 변환은 동일하다는 것을 알 수 있습니다. 문제는, 구하라는 것이 합이 아닌 최댓값이라는 것입니다. 노드의 대표값을 무엇으로 잡는 것이 좋을까요? 예를 들어서, 이런 상황을 생각해 봅시다.

 

 

 해당 노드가 관리하는 구간의 길이가 2이고, v1과 v2가 있었다. 그런데 v1이 v2보다 컸다. 이 두 값에 q를 더했다고 해 봅시다.

 

 

 그러면 v1+q는 v2+q보다 클까요? 아니면 v1+q보다 v2+q가 더 클까요? v1 > v2였으므로, v1+q > v2+q입니다. 이를 일반화 시켜 봅시다. 구간 [A, B]의 최댓값이 v였습니다. 구간 [A, B]에 q를 더했다고 해 봅시다. 그러면, 구간 [A, B]의 최댓값은 v+q가 됩니다. 즉, 우리는, 노드를 대표하는 값을 구간의 최댓값으로 정의하고, q 를더하라는 쿼리가 들어왔을 때 다음과 같이 처리하면 됩니다.

 

 

 [node_s, node_e]의 대표값인, 구간 최댓값을 v'이라 하고, 해당 노드 전체에 q를 더하라는 변환이 들어왔을 때 해당 노드의 대표값을 v'+q로 설정합니다.

 

 

 그리고 변환을 지웁니다. 노드에 q를 더하라는 변환이 흡수되었기 때문입니다.

 

---

 이제 조금 어려운 변환을 보도록 하겠습니다. 업데이트 쿼리가 3개 주어지고, 구간 합을 구하라는 쿼리가 주어집니다. 노드의 대표값을, 노드가 관리하는 구간에 있는 수들의 총 합으로 해야 한다는 것은 알겠습니다.

 

 

 해당 노드에 쿼리 1, 쿼리 2, 쿼리 3, 쿼리 1 등이 누적이 되었다고 해 봅시다. 더하고 곱하고 대입하는 것은 완전히 다른 연산이기 때문에, 이것을 그대로 처리할 수는 없습니다. 대신에, 쿼리 1 ~ 3이 어떤 특수한 형태의 변환으로 나타나는지를 보아야 하는데요.

 

 이를 이렇게 바꿔 봅시다. 쿼리 1은 v를 v+a로 변환합니다. 쿼리 2는 v를 bv로 변환하고, 쿼리3은 v를 c로 변환합니다. 셋 다, f(x) = px + q꼴의 1차 함수로 표현이 가능하다는 것을 알 수 있습니다.

 

 

 그러면 3번이 오고, 다음에 1번이 온 경우에도, Ax + B 변환 다음에 Cx + D 변환이 왔다고 처리할 수 있습니다. 이러한 변환들은 어떻게 누적시키면 좋을까요? 앞에서 말한 합성함수를 이용하시면 됩니다.

 

 

 f(x) = Ax + B이고, g(x) = Cx + D라고 해 봅시다. 그러면 f 변환이 일어난 다음에 g 변환이 일어난 경우에, g(f(x))로 쓸 수 있습니다. 변환을 2번 해 주면 됩니다. 누적된 변환이라는 관점에서 접근하면 된다는 이야기입니다. 수열과 쿼리 13 말고도, 최근에 푼 문제 중에서, 피보나치 머신과 IOI에 출제된 벽이라는 문제가 이 관점에서 접근해야 풀리는 문제입니다. 난이도는 13 < 벽 < 피보나치 머신 정도가 아닐까 싶습니다.

 

 값을 누적시키는 게 아니라 변환을 누적한다. 이것만 기억하셔도 오늘 포스팅에 대한 이해는 무난하게 하실 듯 싶습니다. 다음 시간에는, 어떻게 전파를 시켜야 하는지 보도록 하겠습니다.