lazy propagation segment tree1 #1395 스위치(Segment Tree) 이번 문제는 Platinum III 난이도로 매겨진 좀 난이도가 있는 문제입니다. 기본적으로 이용하는 자료구조는 세그먼트 트리입니다. 세그먼트 트리 자료구조는 제가 나중에 한번 알고리즘적 적용 방법에 대해서 이야기하고자 합니다. 백준 사이트에서 세그먼트 트리와 관련된 문제가 꽤 여러개가 보입니다. 다 난이도가 높게 책정된 문제들입니다. 그런데 세그먼트 트리는 하나의 데이터를 업데이트할 때, \(O(\log N)\) 의 데이터 효율을 가집니다. 그리고 범위에 대해서 연산결과를 내는 것도 역시 \(O(\log N)\)의 효율을 보입니다. 그런데, 범위로 데이터를 업데이트한다고 할 때에는 이게 쉽지 않습니다. 해당 범위내의 것을 모두 업데이트를 일일이 한다고 하면, 세그먼트 트리를 쓰지 않고 배열 자료구조가 .. 2020. 2. 14. 이전 1 다음
