2042번
-
[백준] 구간 합 구하기(2042번)알고리즘/백준 2021. 9. 19. 12:09
문제 링크 풀이 쉬운 문제는 아닙니다. 세그먼트 트리를 이용해야 합니다. 먼저 배열을 통해 살펴보겠습니다. 1. 구간 합 구하기 2. 특정 위치 값 변경 1번의 경우 점화식을 이용해서 푼다면 다음과 같으므로 O(N)입니다. s[0] = a[0]; for (int i = 1; i < n; ++i) { s[1] = s[i-1] + a[i]; } 2번은 a[4] = 3;의 방법으로 이루어지기 때문에 O(1)입니다. 1번이 M번, 2번이 K번 이루어진다면 O(NM + K)입니다. 문제에서 N, M, K는 적은 숫자가 아니기 때문에 O(NM + K)는 충분히 오래 걸릴 수 있습니다. 세그먼트 트리를 이용하면 O((M+K)*log₂N)에 가능합니다. O(NM + K)와 크게 다르지 않은 것처럼 보일 수 있는데, 문..