문제 출처 : 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번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의
www.acmicpc.net
이 문제는 세그먼트 트리라는 기법을 사용해서 문제를 해결하였다.
처음 들어본 기법이고 생소한 기법이라 배우면서 신기했다.
pow 라는 것을 사용하여서 높이 계산을 하여 자식 노드를 먼저 삽입한 뒤 순차적으로 부분합을 구할 수 있었다.
아래는 해당 문제를 풀이한 소스 코드이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include<stdio.h>
#include<cmath>
#pragma warning (disable:4996)
long long int arr[1 << 21]; // 2의 21승 선언 shift
int N, M, K;
long long int sum(int itr, int start, int end, int left, int right)
{
int mid = (start + end) / 2;
if ( end<left || right<start )
return 0;
if (left <= start && end <= right)
return arr[itr];
return sum(itr * 2, start, mid, left, right) + sum(itr * 2 + 1, mid + 1, end, left, right);
}
int main()
{
scanf("%d %d %d", &N, &M, &K);
int size = pow(2, (int)log2(N) + 1);
for (int i = 0; i < N; i++)
scanf("%lld", &arr[size + i]);
for (int i = size - 1; i > 0; i--)
arr[i] = arr[i * 2] + arr[i * 2 + 1]; // 트리 생성
for (int i = 0; i < M + K; i++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (a == 1)
{
int itr = size + b - 1;
int diff = c - arr[itr];
arr[itr] = c;
for (itr = itr / 2; itr > 0; itr = itr / 2)
arr[itr] = arr[itr] + diff;
}
else
{
long long int value = sum(1, 1, size, b, c);
printf("%lld\n", value);
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| 백준 9466번 문제 ( 텀 프로젝트 ) (0) | 2020.04.23 |
|---|---|
| 백준 1039번 문제 ( 교환 ) (0) | 2020.04.20 |
| 백준 5397번 문제 ( 키로거 ) (0) | 2020.02.26 |
| 백준 3079번 문제 ( 입국 심사 ) (0) | 2020.02.26 |
| 백준 16397번 문제 ( 탈출 ) (0) | 2020.02.18 |
뀨심볼
깃허브 주소는 : https://github.com/hhyc2 입니다~