알고리즘/자료구조
2020. 6. 1.
세그먼트 트리 with Lazy propagation
저번 글에서 점 갱신과 구간 연산을 \(O(\log n)\)에 처리할 수 있는 자료구조인 세그먼트 트리에 대해 알아봤습니다. 이번엔 구간 갱신까지 \(O(\log n)\)에 처리하게 해주는 Lazy propagation에 대해 알아봅시다. Lazy propagation을 하기 앞서, 다음 문제를 풀어봅시다. https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 이 문제처럼 구간 갱신이 필요하지만, 구간에 대한 연산결과가 아닌 한 ..
