Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/10999
10999번: 구간 합 구하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
풀이
solved.ac 난이도: Paltium 4
백준- 수열과 쿼리 21(16975)와 동일한 문제.
수열과 쿼리 문제는 펜윅 트리로 풀었지만 위의 문제와 같이 느리게 갱신되는 세그먼트 트리(lazy propagation)로 해결 가능하다. 프로그래밍 분야에서 lazy라는 의미는 계산이 필요할 때까지 최대한 처리를 늦추는 방식을 의미한다.
본 문제의 풀이와 함께 느리게 갱신되는 세그먼트 트리를 설명한 백준님의 게시글을 참조하자.
세그먼트 트리 나중에 업데이트 해야지! - Baekjoon Online Judge
느리게 갱신되는 세그먼트 트리의 핵심은 구간의 값들을 모두 방문해 하나하나 업데이트해주는 것이 아닌
lazy 트리를 추가적으로 이용하여 구간의 값들에 더해 주어야하는 값을 일단 저장만 해둔다.
나중에 해당 구간의 노드를 방문한 경우에만 updateLazy함수를 호출하여 더해주어야하는 값을 추가해준다.
즉, 계산이 필요할 때까지 최대한 처리를 늦춘다.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.17298 - 오큰수 (C++, 스택) (0) | 2021.01.31 |
|---|---|
| [백준] No.2304 - 창고 다각형 (C++, 스택) (0) | 2021.01.30 |
| [백준] No.16975 - 수열과 쿼리 21 (C++, 펜윅 트리) (0) | 2021.01.25 |
| [백준] No.11658 - 구간 합 구하기 3 (C++, 펜윅 트리) (0) | 2021.01.24 |
| [백준] No.2357 - 최솟값과 최댓값 (C++, 세그먼트 트리) (2) | 2021.01.23 |