[BOJ 1395]

문제 바로가기 : https://www.acmicpc.net/problem/1395
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

lazy propagation

세그먼트 트리를 처음 공부할 땐 구간합을 가져올 순 있어도 구간 자체를 업데이트하는건 효율적이지 못했다.
구간에 속하는 리프 노드에 직접 접근하지 않으면서 필요할 때만 업데이트하는 방식을 취함으로써
연산을 빠르게 하는 방법이 있었다. 연산을 미룬다고 해서 lazy propagation 이라고 부른다.

이 알고리즘에 대해서 정말 잘 설명 돼있는 글이 많았다.
여러 곳에서 많이 참고를 했는데 백준에서 본 글이 제일 많이 도움이 됐다! 강추!
~ https://www.acmicpc.net/blog/view/26

review

이 문제는 기본적인 lazy propagation 로직에서 조금 수정해주기만 하면 된다.
일반적으로는 구간 내에 값을 더해주는 연산을 하는데 여기서는 반전시키도록 돼있다.
특정 노드에서 맡고있는 구간 길이는 end-start+1로 나타낼 수 있다. 길이를 8이라고 예를 들자.

1~8번째의 상황이 다음과 같다고 해보자. 켜지면 1, 꺼지면 0이다.
: 1 1 0 1 0 0 1 1

반전 시
: 0 0 1 0 1 1 0 0

5개에서 4개로 바뀌었다.
길이가 9이므로 반전 시에 켜진 개수는 무조건 (길이 - 켜진 개수)가 된다.