[백준][BOJ2042] 구간 합 구하기
1. 문제 : https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 2. 풀이 : Segment Tree 3. 시간복잡도 : O(logN) 4. 설명 입력값 1, 2, 3, 4, 5에 대해 그림[1]과 같은 구간 합 세그먼트 트리를 구현 3번째 수를 6으로 변경하기 위해, 루트에서부터 3~3구간을 관리하는 노드를 탐색하여 값을 변경하고 트리를 업데이트 2번째 수와 5번째 수까지의 구간 합을 ..
Algorithm/Segment Tree
2021. 5. 27. 23:36
