[백준][BOJ2042] 구간 합 구하기

Algorithm/Segment Tree

by bedamino 2021. 5. 27. 23:36

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번째 수까지의 구간 합을 구하기 위해, 루트에서부터 각 구간을 관리하는 노드를 탐색하여 결과값인 17을 return

5. 코드

저작자표시

날마다 새로운 코딩