문제:
어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.
입력:
첫째 줄에 수의 개수 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(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.
입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
출력:
첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.
풀이방법:
세그먼트 트리를 사용해서 푸는 문제다. 세그먼트 트리에 대해서는 추후 자세하게 설명할 예정이다.
우선 현재 가지고 있는 노트의 갯수(N)를 기준으로 트리를 구성한다. 그 다음에 가진 값으로 트리를 채우게 되는데 가장 밑의 leaf는 각 값으로 구성되며, 부모 노드로 올라갈수록 leaf 노드들의 합으로 구성된다.
change를 하는 경우에는 leaf 만을 바꾸는 것이 아니라 상위 노드들도 전부 바꿔야 하고, 부분합을 구하기 위해서는 반으로 나눠 탐색하며 구간에 해당하는 노드 값을 들고 와서 더해주면 된다.
|
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
42
43
44
|
import math
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
segment_tree = [0]*(pow(2,math.ceil(math.log(N,2))+1)-1)
numbers = [int(input()) for _ in range(N)]
def init(node, start, end):
if start == end:
segment_tree[node] = numbers[start]
return segment_tree[node]
else:
segment_tree[node] = init(node*2,start,(start+end)//2) + init(node*2+1, (start+end)//2+1, end)
return segment_tree[node]
def change(node, start, end, idx, diff):
if idx < start or idx > end:
return
segment_tree[node] += diff
if start != end:
change(node*2, start, (start+end)//2, idx, diff)
change(node*2+1, (start+end)//2+1, end, idx, diff)
def subsum(node, start, end, left, right):
if left > end or right < start:
return 0
if left <= start and end <= right:
return segment_tree[node]
return subsum(node*2, start, (start+end)//2, left, right)+ subsum(node*2+1, (start+end)//2+1, end, left, right)
init(1,0,N-1)
for _ in range(M+K):
a, b, c = map(int,input().split())
if a==1:
b -= 1
diff = c - numbers[b]
numbers[b] = c
change(1,0,N-1,b,diff)
else:
print(subsum(1,0,N-1,b-1,c-1))
|
cs |
문제링크:
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
'Algorithm > Python' 카테고리의 다른 글
| [BOJ] 11054. 가장 긴 바이토닉 부분 수열 (0) | 2021.09.02 |
|---|---|
| [BOJ]2565. 전깃줄 (0) | 2021.09.01 |
| [BOJ]2573. 빙산 (0) | 2021.08.30 |
| [BOJ]10942. 팰린드롬? (0) | 2021.08.26 |
| [BOJ]1963. 소수경로 (0) | 2021.08.24 |