느리게2 [백준 10999번] 구간 합 구하기 2 난이도: 플래티넘 IV 문제 링크: 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 그냥 접근하면 시간 초과에 걸리고, 세그먼트 트리를 이용해도 시간 초과에 걸리는 문제입니다. 이 문제를 풀려면 '느리게 갱신되는 세그먼트 트리' 알고리즘을 알아야 합니다. 해당 알고리즘에 대한 자세한 설명은 여기에 있으니 참고해 주세요. 문제를 풀 때 유의할 점은, 문제에서 숫자 배열의 인덱스는 .. 2021. 9. 26. 느리게 갱신되는 세그먼트 트리 세그먼트 트리에 대한 글을 먼저 읽고 와 주시기 바랍니다. 앞서 주어진 배열 arr에 대해, 특정 구간의 합을 O(log N)의 시간 복잡도로 구할 수 있는 알고리즘인 segment tree에 대해 알아보았습니다. 주어진 배열 arr에 대해 미리 구간을 나누어 합을 구한 세그먼트 트리 tree를 만들고, 질의가 들어온 구간에 대해 대표 노드를 선별하여 그 값을 참조하는 방식입니다. 세그먼트 트리는 생성에 O(N log N), 구간 합 구하기에 O(log N), 특정 인덱스의 값 수정에 O(log N)의 시간 복잡도를 가집니다. 그렇다면 다음과 같은 경우를 생각해 봅시다. "특정 구간의 값"을 변경하는 경우가 존재할 수 있습니다. 배열 arr에 대해 구간 [1, 3]의 값에 3씩 더하고, [2, 4]의 구.. 2021. 9. 26. 이전 1 다음
