[ Lazy Propagation ] 개념과 구현방법 (C++)

이 글에서는 'Lazy Propagation' 방법에 대해서 이야기를 해보자.

1. Lazy Propagation ??

먼저 이 글을 읽기 전에 '세그먼트트리(SegmentTree)' 에 대해서 모른다면 세그먼트트리에 대해서부터 알아보고 오자.

세그먼트트리에서 발생할 수 있는 단점과도 같은 상황을 해결하기 위해서 사용되는 방법이 'Lazy Propagation' 이기 때문에

세그먼트트리에 대해서 모른다면 알 필요가 없는 방법이다. 따라서 세그먼트트리에 대해서 먼저 공부를 해오는걸 권장한다.

아래의 링크는 세그먼트트리에 대한 설명을 해놓은 글이다.

[ 세그먼트트리(SegmentTree) 알아보기(Click) ]

세그먼트트리(SegmentTree)는 '구간에 대한 연산'을 처리할 때 굉장히 유용한 자료구조이다. 세그먼트트리에 대해서 설명할 때

크게 2가지 연산을 가정하고 이야기한다. 1. 특정 인덱스의 값을 바꾸는 연산 2. 특정 구간에 대한 합을 구하는 연산

보통 이렇게 2가지 연산에 대해서 이야기를 한다. 위에 링크가 걸려있는 글에서도 그렇게 소개를 했었다.

이번 글에서도 마찬가지로 위의 2가지 연산을 예로 들어서 알아볼 것이다. 그런데 ! 한 가지 연산을 조금 다르게 바꿔보자.

1번연산을 바꿔볼 것인데 1번연산이 이렇게 바뀌었다고 가정해보자.

특정 인덱스의 값 하나만을 변경 → a번 Index부터 b번 Index까지 해당 구간에 있는 모든 값들을 + x 시켜라 !

위의 경우를 한번 생각해보자. 기존의 방법과는 다르게 업데이트를 "구간"의 개념으로 해줘야 한다.

물론 ! 우리가 알고 있듯이 세그먼트 트리로 구현할 수 있다. 해당 Index들을 반복하면서 각각의 Index에 대해 기존의 값과 차이를

구해서 Update함수를 구현해서 호출해주면 된다. 이렇게 구간으로 값을 업데이트 하라고 주어졌음에도 하나하나씩 업데이트를

시키게 된다면, 하나의 값을 업데이트 하는데 걸리는 시간 = logN , 해당 구간의 최댓값 = N , 전체 시간복잡도 = O(NlogN) 으로

꽤 오래 시간이 걸리게 된다는 것을 알 수 있다.

구간에 대한 연산을 빠르게 처리하기 위해서 세그먼트트리를 구현했음에도, 연산이 조금만 바뀌게 된다면 시간이 오래걸린다는

이러한 문제점이 발생한다. 이를 해결하기 위해서 사용되는 방식이 'Lazy Propagation' 이다.

영어 단어 그대로 해석을 해보면 "게으른 전파" 라는 뜻을 가지고 있는데, 이 뜻을 풀어서 이야기해보면 이렇게 이야기할 수 있다.

"나 지금 업데이트 되야 하는 놈인데, 지금 말고  진짜 내가 업데이트가 필요할 때 업데이트 할게 ! 지금은 안할래 !" 이다.

정말 극단적인 예를 한번 생각해보자. 아래에서 말하는 3개의 연산이 순서대로 주어졌다고 가정해보자.

"1번 Index부터 5번 Index까지의 값을 각각 + 3만큼 하세요"

"6번 Index부터 8번 Index까지의 값을 가각 + 4만큼 하세요"

"9번 Index부터 10번 Index까지의 값을 각각 +5만큼 하세요"

이 경우에 과연 모든 노드들을 Update를 해야될 필요가 있는지 한번 생각 해보자. 서로 겹치는 구간이 없기 때문에 서로의 연산은

서로의 연산에 결과를 미치지 못하기 때문에 아무런 노드도 업데이트를 하지 않아도 될까 ??

아니다 ! 분명히 업데이트를 해야될 노드들이 존재하기는 한다. 예를 들어서 세그먼트트리에서 루트노드를 생각해보자.

루트노드 같은 경우에는 모든 범위를 포함하고 있는 노드이기 때문에, 위의 3가지 연산들에 대해서 영향을 미치게 된다. 따라서

루트노드를 포함해서 해당 구간에 대한 범위를 포함하고 있는 노드들 일부는 업데이트가 되어야 한다.

그런데 ! 과연 리프노드까지 내려가서 1번 Index의 값을 바꾸고, 2번 Index의 값을 바꾸고, 1 - 2번 Index에 대한 구간 결과값을 갖는 노드의 값을 바꾸고, 3번 Index의 값을 바꾸고, 4번 Index의 값을 바꾸고.. 정말로 필요가 있는 연산들일까 ??

정말로 필요하다고 생각해서 실제로 바꾸는 연산을 진행했다면, 첫 번째 연산을 진행하고 두 번째 연산을 진행할 때 그 바꿨던 행위들이 영향을 미치게될까 ?? 그렇지 않다. 왜냐하면 찾고자 하는 구간의 범위가 다르기 때문에 영향을 미치지 않는다.

하지만 ! 위의 3개의 연산 이후에 4번째 연산으로 "3번부터 10번 Index까지의 구간 합을 구하세요" 라는 명령이 떨어진다면

이야기가 달라진다. 왜냐하면 정확한 값을 구하기 위해서는 기존에 업데이트된 값을 가지고 있어야 하기 때문에 이런 경우에는

업데이트를 해줘야 한다.

즉 ! "구간에 대한 값 변경 명령이 떨어졌을 때, 일부 노드들은 반드시 업데이트 되어야 한다. 하지만 ! 일부 노드들은 반드시 업데

이트 될 필요 없이, "업데이트를 해야하는 노드입니다" 라고 알 수 있도록 표시만 해주고 그 다음 또 다른 명령어를 실행할 때 해당 명령어를 실행하기 위해서 업데이트가 필요하다면, 그 때 업데이트를 하는 방식" 이 게으른 전파, 즉, Lazy Propagation 이다.

쉽게 이야기해서 업데이트를 최대한 미룰 수 있을 때 까지 미룸으로써, 업데이트 하는 시간을 최소화 시키는 방법이다.

2. Lazy Propagation 동작원리

Lazy Propagation이 동작하는 방법에 대해서 알아보자.

먼저 또 다른 vector 혹은 배열이 하나 더 필요하다. 바로 위에서 이야기했던 "업데이트를 해야하는 노드입니다" 라고 알 수 있도록 표시를 해 줄 만한 놈이 필요한 것이다. 크기는 당연하게도 세그먼트트리의 크기와 동일하다.

본인은 vector로 구현했으니 이 글에서도 vector로 설명하겠다. (vector<int> Lazy)

초기 모든 값이 0으로 초기화 되어있는 Lazy vector를 이용해서 "업데이트를 할 필요가 있는지 없는지" 에 대해서 체크할 것이다.

크기가 10인 원본 배열이 하나 있다고 가정하자. 해당 배열은 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } 의 값을 가지고 있다.

이 때, 해당 배열에 대한 세그먼트 트리를 구성해보면 다음과 같은 형태일 것이다.

위의 그림을 보면 한 노드당 숫자가 2개씩 적혀있다. 윗줄에 한개, 아랫줄에 한개.

윗줄은 해당 노드가 포함하고 있는 구간을 나타낸 것이다. 리프노드는 구간이 아닌 배열의 값을 그대로 가지기 때문에, 숫자의 형태가 a-b 가 아닌 숫자 하나만 적혀있고, 리프노드가 아닌 노드들은 구간에 대한 정보를 담고 있다.

아랫줄에 적혀있는 숫자는 세그먼트 트리에 저장되어 있는 "구간 합"에 대한 결과값을 적어놓은 것이다.

여기서 "3번 Index부터 4번 Index사이에 있는 모든 값들을 + 2 만큼의 연산을 진행하세요" 라는 명령이 떨어졌다고 생각해보자.

그럼 이 명령에 의해서 영향을 받는 노드들을 먼저 체크해보자.

위와 같이 파랑색과 주황색으로 으로 칠해놓은 노드들이, 3번 Index의 값과 4번 Index의 값이 + 2가 됨으로써 영향을 미치는 노드들이다. 파랑색과 주황색의 색깔 차이는 밑에서 알아보자.

여기서 세그먼트 트리를 공부할 때, "구간합"을 구하는 Query과정을 다시한번 생각해보자.

지금은 값을 Update하는 과정인데, 왜 갑자기 구간합이 나오는 것일까 ?? 왜냐하면 위에 링크를 걸어놓은 본인이 설명해놓은

세그먼트 트리에 대한 글에서 Update할 때에는, 하나의 Index만 가지고 구했기 때문에 Update를 구현한 내용에 구간에 대한

판별을 하는 과정이 없기 때문이다. 그래서 잠시 "구간합"을 구하는 방식을 이용해서 아이디어를 빌려와보고자 한다.

'특정 구간에 대한 연산'을 진행할 때는 크게 3가지로 나눌 수 있다.

1. 현재 우리가 탐색하는 범위가, 우리가 찾고자 하는 구간과 완전히 겹쳐지지 않은 경우.

2. 현재 우리가 탐색하는 범위가, 우리가 찾고자 하는 구간에 완전히 속해있는 경우.

3. 1, 2번을 제외한 나머지 경우. 즉, 일부만 걸쳐있는 경우

우리는 이 3가지 경우를 "구간에 대한 Update"를 할 때 사용할 것이다. 왜냐하면 우리가 지금 하는 것이 "a ~ b번 Index의 값들을

모두 + 2씩 하세요~" 와 같은 연산을 할 것이기 때문에, 구간 업데이트가 필요하기 때문이다.

먼저 첫 번째 Case. 우리가 업데이트를 하고 싶어하는 구간과, 현재 구간이 완전히 겹쳐져 있지 않다면 더 이상의 탐색은

필요 없다. 업데이트 또한 필요 없다.

두 번째 Case를 이야기하기 전에, 먼저 세 번째 Case부터 보자. 우리가 업데이트를 하는 구간과, 현재 구간이 일부만

걸쳐있는 경우에는 왼쪽 자식노드, 오른쪽 자식 노드로 까지 탐색을 더 진행해 보아야 한다.

우리가 주목해야 할 것은 두 번째 Case이다. 현재 구간이, 우리가 업데이트 하고자 하는 구간에 완전히 속해있는 경우이다.

기존에 Update가 아닌,  "구간합"을 구하는 함수에서는 이 경우 해당 노드를 return 함으로써 추가적인 탐색을 필요로 하지 않았다.

그런데 ! 우리는 단순 구간합이 아닌, 값을 업데이트 해야 하고 이 글의 주 목표인 'Lazy Propagation'도 진행해야 한다.

본격적으로 두 번째 Case에 대한 이야기를 진행해보자. 위의 그림을 다시 가져와보자.

과연 두 번째 케이스에 걸리는 노드는 무슨 노드일까 ?? 주황색 노드가 두 번째 케이스에 걸리는 노드이다.

우리가 업데이트를 하고자 하는 구간 : [ 3 , 4 ]

파랑색으로 표시되어있는 루트노드의 구간 : [ 0 , 9 ]

먼저 루트 노드의 경우에는 왼쪽자식노드, 오른쪽자식 노드까지 탐색을 해봐야 하는 노드이다. 즉, 3번 경우에 해당한다.

이 경우에는 세그먼트 트리의 업데이트 과정과 같이 똑같이 업데이트를 해야 한다. 즉 ! 우리가 위에서 말했던

"일부의 노드는 업데이트 되어야 한다" 에서 "일부의 노드"에 포함되는 노드이다.

그 아래에 있는 노드의 구간 : [ 0 , 4 ]

이 경우도, 일부만 걸쳐있기 때문에, 3번 경우에 해당한다. 왼쪽 자식과 오른쪽 자식 노드 까지 모두 탐색을 해봐야 한다.

이 또한, 위에서 말했던 업데이트 되어야 하는 "일부의 노드" 이다.

그 아래에 있는 "주황색" 노드의 구간 : [ 3 , 4 ]

우리가 업데이트를 하고자 하는 구간안에 완전히 속해있는 구간이다. 우리는 이 구간에서 'Lazy Propagation' 을 사용할 것이다.

우리는 해당 노드까지만 업데이트를 하고, 그 밑에 있는 자식 노드들에 대해서는 업데이트를 하지 않을 것이다. 대신 ! 언젠가는

이 업데이트를 하지 않은 노드들을 사용해야하는 순간이 올 수도 있기 때문에, "업데이트를 해야 하는 노드입니다" 라고 알 수 있도록 표시는 해놓을 것이다.

그럼 해당 노드까지만 업데이트를 해보자. 어떻게 될까 ? 3번 Index와 4번 Index의 값을 + 2 씩 하기 때문에, 주황색 노드의 값은

결과적으로 + 4 가 되어야 한다. 이 후, 'Lazy Propagation'이 아니라면 해당 자식의 노드들도 값을 업데이트 해야 하겠지만,

하지 않을 것이다. 즉 ! 세그먼트 트리가 이렇게 될 것이다.

보게 되면, 주황색 위에 있는 2개의 파랑색 노드들은 값이 + 4 로 업데이트 되었고, 주황색 노드까지도 업데이트가 되었지만 주황색 노드의 자식 노드들은 + 2로 업데이트 하라는 명령이 있음에도 업데이트 되지 않았다는 것을 볼 수 있다.

계속해서 이야기했지만, 우리는 이 노드들에게 표시를 해줘야한다. "업데이트 해야하는 노드입니다" 라고 알 수 있도록 !

이 때, 우리가 위에서 선언해놓은 vector<int> Lazy 를 사용해보자. 먼저, Lazy에 대해서 설명을 하자면 Lazy[a] = b 의 의미는

"a번 노드는 b만큼 값이 업데이트 되어야 하는데, 업데이트를 하지는 않고 미루고 있는 중입니다. 그러니까 이 노드를 사용하시려면 업데이트를 한 후에, 사용하세요 !" 를 의미한다.

즉, 3번과 4번 노드에는 다음과 같이 Lazy값이 표시가 된다.

이렇게 해놓으면 다음번에 위의 노드들을 사용하려면 Lazy값을 확인만 해보면 된다. Lazy의 값이 0이라면 업데이트를 할 필요가

없는 노드라는 것을 의미하고, Lazy의 값이 0이 아니라면 업데이트를 해야 하는데 하지 않고 미루고 있는 노드 라는 것을 의미한다.

따라서, Lazy값이 0이 아닌 경우에는 업데이트를 진행 후, 연산을 진행하면 된다.

그런데 ! 우리가 알아보지 않고 지나간 부분이 하나 있다. 바로 주황색 노드를 구할 때 이다. 자연스럽게 3번 Index에 + 2, 4번 Index에 + 2 가 진행되므로, 주황색 노드는 결과적으로 + 4 가 진행될 것이다 라고 이야기했는데, 이 부분을 조금 구체적으로 알아보자.

우리가 +4 라는 숫자를 알아낼 수 있었던 건, 주황색 노드가 담당하고 있는 노드의 갯수가 2개라는 것을 알아서 그런 것이였고, 그 값이 '2' 라는 것을 알고 있었기 때문이다. 그럼 상황을 바꿔보자. 만약에, 루트노드의 왼쪽 자식 노드인 0 ~ 4를 담당하고 있는

노드가 주황색 노드라면 어떻게 갱신을 해줘야할까 ??

0 ~ 4가 의미하는 것은, 배열의 0번 Index부터 4번 Index 까지의 값을 관리하고 있다는 것을 의미한다. 즉 ! 총 5개의 배열의 값을

관리하고 있음을 의미한다. 이 '5개' 라는 값을 일반화를 시켜보면 다음과 같다.

End - Start + 1 ! 바로 각 노드들이 담당하고 있는 구간의 마지막 구간의 Index값 - 시작 구간의 Index값 + 1을 한 것이

해당 노드가 관리하고 있는 노드의 갯수이다.

다시 원래대로 돌아와서 3 - 4 로 표시된 주황색 노드에 + 4를 할 수 있었던 이유를 일반화를 시켜서 이야기해보면

"주황색 노드는 4 - 3 + 1 = 2. 즉 ! 2개의 배열의 값을 관리하고 있기 때문에, 해당 배열의 값들이 + 2 씩 되기 때문에 2 x 2 = 4로

결과적으로 + 4의 결과를 얻습니다." 라고 이야기할 수 있다.

즉 ! 주황색 노드들을 업데이트 할 때에는, (End - Start + 1) * Value 로 업데이트를 진행해 주어야 한다. 단순 + 로 진행하면 안된다 ! Lazy Propagation의 전체적인 원리가 이렇다. 그러면 조금만 더 어려운 예시를 통해서 한번만 더 진행해보자.

위의 상태를 그대로 가지고 온 것이다. 이 후 ! "3번 Index부터 9번 Index까지 모든 값들을 + 1 시키세요!" 라는 연산이 떨어졌다.

마찬가지로 먼저 영향을 미치는 노드들을 보면 다음과 같다.

이번에도 역시 파랑색 노드가 있고 노랑색 노드들이 있다. 파랑색 노드들은 마찬가지로 업데이트가 바로바로 일어날 노드들이다.

하지만 노랑색 노드들은 그렇지 않다. 왜냐하면 3 ~ 9의 범위에 완전히 포함되는 노드들이기 때문에 해당 노드들 까지만 업데이트를 진행해줄 것이고, 그 밑에 자식 노드들은 업데이트 해주지 않을 것이다.

그럼 어떻게 될까? 먼저 3 - 4 의 구간을 담당하고 있는 노랑색 노드를 보자. 해당 값은 업데이트 될 것이다. 무슨값으로 ?

(4 - 3 + 1) * 1 = 2. 즉, 13에서 15의 값으로 Update될 것이다.

그럼 그 밑에 있는 자식 노드들은 어떻게 될까 ? 당연히 업데이트를 하지 않을 것이다. 그런데 ! 기존에 이미 업데이트를 해야 될

값이 존재하잖아 ?? 그냥 그 값이 더해주면 된다. 아래 그림과 같이 !

위의 그림은 루트노드를 기준으로 왼쪽 자식들만 업데이트를 해놓은 결과이다. 오른쪽 자식은 아직 업데이트 하기 전이다 !

보게 되면, 파랑색 노드들과 노랑색 노드는 업데이트 됬지만, 초록색 노드들은 업데이트 되지 않고 값이 그대로인 것을 볼 수 있다.

대신, 그 노드들에는 Lazy값이 첫 번째 연산에 의해서 + 2가, 두 번째 연산에 의해서 + 1 이 붙어서 총 +3의 값이 붙어있음을

확인할 수 있다. 다시한번 말하지만 이 값은 "이 노드들은 업데이트 되야 하는데 지금 미루고 있습니다 ! 이 노드들을 쓰시려면

+3만큼의 값으로 업데이트 하신 후 사용하세요 !" 라는 것을 의미하고 있다.

이제 오른쪽 노랑색 노드인 5 - 9 로 가보자. 이 경우도 마찬가지로 3 - 9 에 완전히 포함된 경우이기 때문에 2번 Case이다.

마찬가지로 해당 노드 까지만 업데이트 하고 업데이트 하지 않을 것이다. 대신 ! Lazy값을 표시해줄 것이다. 다음과 같이 !

노랑색 노드는 (9 - 5 + 1) * 1 의 값만큼 + 되어서 40 에서 45로 값이 업데이트 되었다. 하지만 자식노드들에게는 Lazy값만 주고

업데이트를 진행하지 않았다. 여기서 하나의 연산만 더해보자. "4번 Index에서 8번 Index까지의 구간합을 구하세요" 가 주어졌다고

생각해보자. 먼저, 우리가 찾아봐야할 노드들을 색깔로 칠해보자.

보기 편하게 세그먼트 트리에서의 노드 번호들을 빨강색으로 적어왔다.

먼저, 1번 노드는 일부만 걸친 경우이기 때문에 2번노드 3번노드 모두 탐색을 진행할 것이다.

2번 노드에서는 4번 노드와 5번 노드로 가겠지만, 4번 노드는 완전히 겹치지 않는 구간이기 때문에 0을 return받을 것이기 때문에

실제로 방문하는 노드이기는 하지만 파랑색으로 칠하지는 않았다.

5번 노드 또한 일부만 걸친 경우이기 때문에 자식노드인 10번 노드와 11번 노드 모두 탐색을 진행할 것이다.

그런데 ! 10번 노드와 11번 노드를 탐색하러 들어가보니, Lazy값이 존재하는 노드들이다. 우리는 이 값을 통해서 "기존에 업데이트를 해야하는 노드들이였지만, 미루고 있는 노드들이다 ! 지금 이 값을 사용해야 하니 업데이트를 진행하자 !" 라고 생각할 수 있다.

그럼 이 타이밍에 10번 노드와 11번 노드가 업데이트 될 것이다. 사실 10번 노드 같은 경우는 범위 밖을 벗어나는 노드라서 어차피

0을 return받을 노드이지만, 일단 이 노드를 방문하는 순간 업데이트는 진행하게 된다. 즉 위의 노드가 다음과 같은 상태로 변하게 된다.

10번과 11번 노드를 보게 되면 값이 업데이트 되고, Lazy의 값이 다시 0으로 바뀐 것을 확인할 수 있다.

( 우리가 지금 해결하고 있는 명령어는 4 - 8에 대한 구간합을 진행하고 있지만, 구간합을 구하는 과정보다는 Lazy Propagation에

  포커싱을 맞춰서 진행하겠습니다. )

이제 루트노드의 왼쪽자식 노드는 모두 탐색했으니 이제 오른쪽 자식 노드로 가보자.

3번 노드의 경우에는 4 - 8 과, 5 - 9의 관계이니 왼쪽 자식과 오른쪽 자식 모두 탐색을 해줘야 한다.

6번 노드로 가니, Lazy의 값이 있다. 이 노드를 사용해야 하는데 업데이트를 하지 않은 노드이다. 일단 업데이트를 해주자 !

그런데 ! 여기서 어떻게 해야할까 ? Lazy의 값이 있어서 Update를 하는데, 6번 노드만 Update를 하면 될까 ??

이 경우는 아까 10번과 11번 노드와는 달리, Lazy의 값이 존재하고, 해당 노드의 자식노드들 또한 존재하는 경우이다.

이런 경우에는 해당 노드를 Update한 후에, Lazy의 값을 자식들에게 물려주게 된다.

일단 6번 노드를 Update하게 되면, (7 - 5 + 1) * 1 = 3 으로 + 3 만큼 값이 업데이트 하게 된다. 그 이후 ! 자식들에게 해당 노드의

Lazy값을 물려주어야 한다. 왜냐하면 ! 6번 노드 같은 경우에는 우리가 찾고자 하는 범위인 4 - 8 구간에 완전히 속한 노드이다.

따라서 지금 당장 6번 노드를 써야 하는데, Lazy의 값이 있기 때문에 업데이트를 하는 것은 당연하다. 하지만, 그 밑에 자식들인

12, 13, 24, 25번 노드들은 업데이트를 지금 당장 꼭 해줘야할까 ?? 아니다. 우리는 6번 노드의 결과만 있으면 우리가 원하는 정답을 구하는데 지장이 없다. 밑에 노드들을 업데이트 할 필요가 없다. 하지만 ! 우리가 두 번째 진행했던 연산을 보면

"3번 Index부터 9번 Index까지의 값들을 +1 시키세요" 였는데, 이 연산을 제대로 진행했다면 위에서 말한 12, 13, 24, 25번 노드들

또한 업데이트가 되어야 맞는 상황이다. 즉 ! 이렇게 Lazy값이 있는 노드를 계산할 때는, 해당 자식노드들 까지 업데이트 할 필요는

없지만 Lazy의 값을 물려주어야 한다.

7번 노드를 한번 보자. Lazy의 값이 있으므로 일단 업데이트를 해주자. (9 - 8 + 1) * 1 = 2. 값이 19에서 + 2 되어서 21이 될 것이다.

그 이후, 자식 노드들이 있으니 해당 Lazy값을 자식들에게 물려주자. 즉, 14번노드와 15번 노드에 Lazy값이 '1'이 생길 것이다.

7번 노드의 경우는 [ 8 , 9 ]의 구간을 관리하므로, [ 4 , 8 ]에 일부만 걸치는 경우이다. 따라서 왼쪽 자식 오른쪽 자신 모두

탐색을 해봐야 하는데, 왼쪽 자식, 오른쪽 자식 모두 Lazy값이 있으므로 업데이트가 진행된 후에 결과를 가져오게 된다.

해당 연산까지 모두 진행한 후의 결과는 다음과 같다.

3. Lazy Propagation 구현하기

구현하는 것은 크게 복잡하지는 않다. 위의 내용을 이해하고 아는 것이 훨씬 더 어려운 일이지 실제 구현은 그리 복잡치 않다.

우리는 Lazy Propagation을 할 때 가장 우선적으로 처리해줘야 할 일이 하나 있다.

바로, "어떤 명령어가 떨어지더라도, Lazy의 값을 우선적으로 확인하는 것" 이다. Lazy의 값이 있다면 해당 값부터 업데이트 한 후에 진행을 해야 올바른 정답을 얻을 수 있기 때문이다.

따라서, 특정 구간에 대한 값들을 업데이트해라, 특정 구간에 대한 합을 구해라, 이러한 연산들이 떨어질 때 항상 먼저 Lazy의 값을

확인해 주어야 한다.

Lazy값을 업데이트 하는 부분부터 알아보자.

void Lazy_Update(int Node, int Start, int End)
{
    if (Lazy[Node] != 0)
    {
        SegmentTree[Node] = SegmentTree[Node] + (End - Start + 1) * Lazy[Node];
        if (Start != End)
        {
            Lazy[Node * 2] = Lazy[Node * 2] + Lazy[Node];
            Lazy[Node * 2 + 1] = Lazy[Node * 2 + 1] + Lazy[Node];
        }
        Lazy[Node] = 0;
    }
}

Lazy 노드의 값이 0일 때만 업데이트를 해주면 된다.

line5)에서 보면, 위에서 말했던 "주황색 노드"를 업데이트 하는 과정이다.

업데이트는 단순 + 연산이 아닌, (End - Start + 1) * Lazy_Value 로 해주어야 한다 !

line6)을 보면, 리프노드가 아닌 경우, Lazy의 값을 자식들에게 물려준다고 했다. 그 과정을 나타낸 것이다.

line11)을 보면, 업데이트를 진행했음으로, 해당 노드의 Lazy 값은 다시 0이 된다!

아래의 코드는 Update하는 과정이다.

void Update(int Node, int Start, int End, int Left, int Right, ll Value)
{
    Lazy_Update(Node, Start, End);
    if (Right < Start || Left > End) return;
    if (Left <= Start && End <= Right)
    {
        SegmentTree[Node] = SegmentTree[Node] + (End - Start + 1) * Value;
        if (Start != End)
        {
            Lazy[Node * 2] = Lazy[Node * 2] + Value;
            Lazy[Node * 2 + 1] = Lazy[Node * 2 + 1] + Value;
        }
        return;
    }
 
    int Mid = (Start + End) / 2;
    Update(Node * 2, Start, Mid, Left, Right, Value);
    Update(Node * 2 + 1, Mid + 1, End, Left, Right, Value);
    SegmentTree[Node] = SegmentTree[Node * 2] + SegmentTree[Node * 2 + 1];
}

line3) 위에서 계속 말했듯이, Lazy의 값을 먼저 확인하고 해당 노드를 업데이트 하는 것이 가장 우선적으로 처리해줘야 할 일이다.

line4)는 완전히 범위를 벗어난 경우, line5)가 우리가 말했던 "2번째 경우"에 해당하는 Case이다. 현재 노드가 담당하는 구간이, 내가 찾고자 하는 구간에 완전히 속해 있는 경우이다. 이 경우에는 해당 노드 까지만 업데이트를 시켜준 후, 그 아래 자식 노드들은

업데이트 하지 않고, Lazy값만 표시해 준다고 했다. line8 ~ 13)이 그 과정을 나타낸 것이다.

ll Query(int Node, int Start, int End, int Left, int Right)
{
    Lazy_Update(Node, Start, End);
    if (Right < Start || Left > End) return 0;
    if (Left <= Start && End <= Right) return SegmentTree[Node];
 
    int Mid = (Start + End) / 2;
    ll Left_Result = Query(Node * 2, Start, Mid, Left, Right);
    ll Right_Result = Query(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Left_Result + Right_Result;
}

이 코드는 구간합을 구하는 부분인데, 세그먼트 트리와 동일하다. 단지, line3)에서 볼 수 있듯이, Lazy값을 업데이트 하는 과정만

추가되었을 뿐이다.

이렇게 Lazy Propagation에 대해서 알아보았다. 아래 소스코드는 Lazy Propagation에 대한 전체 소스코드이고, 실행결과창은

우리가 위에서 진행했던 3가지 연산에 대한 출력값이다.

1. 3번Index ~ 4번 Index의 값을 + 2 씩 하세요.

2. 3번Index ~ 9번 Index의 값을 + 1 씩 하세요.

3. 4번Index ~ 8번 Index의 구간합을 구하세요.

이 3가지 연산에 대한 세그먼트 트리의 값과, Lazy값을 출력한 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 1000010
typedef long long ll;
using namespace std;
 
int N, M, K;
int Arr[MAX];
vector<ll> Lazy;
vector<ll> SegmentTree;
vector<pair<pair<int, int>, pair<int, int>>> Cmd;
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) cin >> Arr[i];
    for (int i = 0; i < M + K; i++)
    {
        int a; cin >> a;
        if (a == 1)
        {
            int b, c, d; cin >> b >> c >> d;
            Cmd.push_back(make_pair(make_pair(a, b), make_pair(c, d)));
        }
        else
        {
            int b, c; cin >> b >> c;
            Cmd.push_back(make_pair(make_pair(a, b), make_pair(c, -1)));
        }
    }
}
 
ll Make_SegmentTree(int Node, int Start, int End)
{
    if (Start == End) return SegmentTree[Node] = Arr[Start];
 
    int Mid = (Start + End) / 2;
    ll Left_Result = Make_SegmentTree(Node * 2, Start, Mid);
    ll Right_Result = Make_SegmentTree(Node * 2 + 1, Mid + 1, End);
    SegmentTree[Node] = Left_Result + Right_Result;
 
    return SegmentTree[Node];
}
 
void Setting_SegmentTree()
{
    int Tree_Height = (int)ceil(log2(N));
    int Tree_Size = (1 << (Tree_Height + 1));
    SegmentTree.resize(Tree_Size);
    Lazy.resize(Tree_Size);
    Make_SegmentTree(1, 0, N - 1);
}
 
void Lazy_Update(int Node, int Start, int End)
{
    if (Lazy[Node] != 0)
    {
        SegmentTree[Node] = SegmentTree[Node] + (End - Start + 1) * Lazy[Node];
        if (Start != End)
        {
            Lazy[Node * 2] = Lazy[Node * 2] + Lazy[Node];
            Lazy[Node * 2 + 1] = Lazy[Node * 2 + 1] + Lazy[Node];
        }
        Lazy[Node] = 0;
    }
}
 
void Update(int Node, int Start, int End, int Left, int Right, ll Value)
{
    Lazy_Update(Node, Start, End);
    if (Right < Start || Left > End) return;
    if (Left <= Start && End <= Right)
    {
        SegmentTree[Node] = SegmentTree[Node] + (End - Start + 1) * Value;
        if (Start != End)
        {
            Lazy[Node * 2] = Lazy[Node * 2] + Value;
            Lazy[Node * 2 + 1] = Lazy[Node * 2 + 1] + Value;
        }
        return;
    }
 
    int Mid = (Start + End) / 2;
    Update(Node * 2, Start, Mid, Left, Right, Value);
    Update(Node * 2 + 1, Mid + 1, End, Left, Right, Value);
    SegmentTree[Node] = SegmentTree[Node * 2] + SegmentTree[Node * 2 + 1];
}
 
ll Query(int Node, int Start, int End, int Left, int Right)
{
    Lazy_Update(Node, Start, End);
    if (Right < Start || Left > End) return 0;
    if (Left <= Start && End <= Right) return SegmentTree[Node];
 
    int Mid = (Start + End) / 2;
    ll Left_Result = Query(Node * 2, Start, Mid, Left, Right);
    ll Right_Result = Query(Node * 2 + 1, Mid + 1, End, Left, Right);
    return Left_Result + Right_Result;
}
 
void Solution()
{
    Setting_SegmentTree();
    cout << "==================================================================" << endl;
    cout << "Tree = [ ";
    for (int j = 1; j < SegmentTree.size(); j++)
    {
        printf("%3d ", SegmentTree[j]);
    }
    cout << "]"; 
    cout << endl;
    cout << "Lazy = [ ";
    for (int j = 1; j < SegmentTree.size(); j++)
    {
        printf("%3d ", Lazy[j]);
    }
    cout << "]";
    cout << endl;
    cout << "==================================================================" << endl;
    for (int i = 0; i < M + K; i++)
    {
        int Command = Cmd[i].first.first;
        if (Command == 1)
        {
            int Index = Cmd[i].first.second - 1;
            int Index2 = Cmd[i].second.first - 1;
            ll Value = Cmd[i].second.second;
 
            Update(1, 0, N - 1, Index, Index2, Value);
        }
        else
        {
            int Index = Cmd[i].first.second - 1;
            int Index2 = Cmd[i].second.first - 1;
            cout << Query(1, 0, N - 1, Index, Index2) << endl;
        }
 
        cout << "==================================================================" << endl;
        cout << "Tree = [ ";
        for (int j = 1; j < SegmentTree.size(); j++)
        {
            printf("%3d ", SegmentTree[j]);
        }
        cout << "]";
        cout << endl;
        cout << "Lazy = [ ";
        for (int j = 1; j < SegmentTree.size(); j++)
        {
            printf("%3d ", Lazy[j]);
        }
        cout << "]";
        cout << endl;
        cout << "==================================================================" << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}