#1395 스위치(Segment Tree)

이번 문제는 Platinum III 난이도로 매겨진 좀 난이도가 있는 문제입니다.

 

기본적으로 이용하는 자료구조는 세그먼트 트리입니다.  세그먼트 트리 자료구조는 제가 나중에 한번 알고리즘적 적용 방법에 대해서 이야기하고자 합니다.  

 

백준 사이트에서 세그먼트 트리와 관련된 문제가 꽤 여러개가 보입니다.  다 난이도가 높게 책정된 문제들입니다.  그런데 세그먼트 트리는 하나의 데이터를 업데이트할 때, \(O(\log N)\) 의 데이터 효율을 가집니다.  그리고 범위에 대해서 연산결과를 내는 것도 역시 \(O(\log N)\)의 효율을 보입니다.  그런데, 범위로 데이터를 업데이트한다고 할 때에는 이게 쉽지 않습니다.  해당 범위내의 것을 모두 업데이트를 일일이 한다고 하면, 세그먼트 트리를 쓰지 않고 배열 자료구조가 더 효율적입니다.  그래서 나오는 것이 게으른 전달 방식의 세그먼트 트리(Lazy Propagation Segment Tree)입니다.

 

게으른 전달 방식의 세그먼트 트리를 쓰기 위해서는 트리의 루트 노드에다가 업데이트가 있다는 표시를 해주어야 하고, 트리의 값을 미리 계산할 수 있어야 합니다.  예를 들어서 31~70 까지의 범위에 있는 배열값을 1씩 증가시킨다고 한다면, 31~70 사이에 있는 트리의 노드의 트리값을 우리가 미리 계산해서 적용할 수 있습니다.

 

Lazy propagation Segment Tree

위 그림과 같이 현재 스위치가 모두 꺼진 세그먼트 트리(모든 노드값이 0인)가 있습니다.  여기서 3부터 6까지의 스위치를 반전시키겠다고 한다면,  루트부터 시작하게 됩니다.  1번 노드에서는 3부터 6범위는 1번 노드 범위인 1부터 7범위를 포함하지 않으므로 분기를 합니다.  2번 노드에서는 1부터 4이니까 또 분기를 하겠죠.  4번 노드에서는 1-2까지이니까 업데잇 없이 0을 반환하고, 5번 노드에서는 3-4까지이므로 여기서 더 아래로 내려가지 않고, lazy를 선언하고, 0을 2로 바꾸어줍니다.  5번 노드에서의 범위가 3-4이므로 배열 범위는 2개이고, 현재 켜진 스위치 갯수가 0이므로 노드값은 2-0 = 2가 되어 그 숫자를 반환합니다.  lazy가 선언된 노드값은 변경이 완료되었지만, 그 노드의 자식노드들은 반영이 늦게 되는 구조가 됩니다.  이런 형태로 늦게 데이터를 반영한다면, 전체 업데잇시간을 \(O(\log N)\)으로 줄일 수 있습니다.

 

게으른 전달의 세그먼트 트리가 가능하려면, 트리의 노드값을 자식 노드를 둘러보지 않고 업데잇할 수 있어야 한다는 점입니다.  이 문제에서는 스위치를 반전시키는 것이므로, 켜져있는 스위치의 갯수는 범위내 스위치 갯수에서 현재 켜져있는 스위치 갯수가 됩니다.  이것만 염두에 둔다면, 세그먼트 트리 기법을 알고 있다면, 어렵지 않게 풀 수 있습니다.