segment3 느리게 갱신되는 세그먼트 트리 세그먼트 트리에 대한 글을 먼저 읽고 와 주시기 바랍니다. 앞서 주어진 배열 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. [백준 2042번] 구간 합 구하기 난이도: 골드 I 문제 링크: 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 이 문제는 세그먼트 트리라는 알고리즘을 알아야 풀 수 있는 문제입니다. 기본적인 설명은 여기를 참고해 주세요. 세그먼트 트리의 기본적인 문제입니다. 한 가지 유의할 점이 있다면, 값을 수정할 때입니다. b의 값을 c만큼 수정하는 것이 아니라, b의 값을 c로 수정하는 것입니다. 따라서 차이값 differenc.. 2021. 9. 25. 세그먼트 트리 다음과 같은 문제를 생각해 봅시다. 배열 arr에는 수많은 int형 정수가 들어 있다. arr의 크기 n은 최대 10만이며, 각 정수는 1000 이하의 크기를 가진다. 배열이므로, 당연히 arr의 모든 원소는 인덱스가 정해져 있다. 인덱스는 0부터 시작한다. 총 m줄에 걸쳐 구간이 주어질 때, 주어진 구간합을 출력하는 코드를 작성하시오. (n 2021. 9. 25. 이전 1 다음
