백준(2042,10868)
세그먼트트리(Sum, ChangeValue, Min)
백준(2042,10868)
구간합 구하기3(2042)
어떤 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보다 작거나 같은 정수이다.
- 입출력 예시
5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5
--------------
17
12
해결책
단순히 구간의 합을 구하는 문제가 아닌 중간에 원소가 빈번히 변하기때문에 시간복잡도를 생각해야한다. 그러므로 이 문제는 세그먼트트리를 이용하여 해결하였다.
문제가 원하는 것은 원소의 변경, 구간합 두가지이기때문에, 원소변경과 구간합만 작성해서 해결한다.
- 세그먼트트리(구간합전용) 생성하기
일단 트리를 구성할때, 전체원소의개수 k에서 전체 리스트의 사이즈는 2^k*2로 선언하도록 하고, 원소의 값을 담을 인덱스 시작값은 2^k부터이다. 또한 이진트리에서 왼쪽하위노드는 루트노드의 *2 , 오른쪽하위노드는 *2+1이므로 리스트의 끝에서 2로 나누어주면서 누적을 하며 값을 초기화시킨다.
- 값 변경
구성된 트리에서 값을 변경한다면,
- 구간합구하기
start≤end의 조건하에서
start%2==1이면
누적해주고, start+=1
end%2==0이면
누적해주고, end-=1
start/=2
end/=2
코드
import sys
input = sys.stdin.readline
n,chnage,sum = map(int,input().split())
treeSize=1
tmp=n
while tmp!=0:
tmp=tmp//2
treeSize *=2
treeSize=treeSize * 2
startIndex = treeSize//2
tree = [0] * (treeSize+1)
def change_node(a,value):
global tree
dif=value-tree[a]
while a>0:
tree[a]+=dif
a=a//2
def subnet_sum(start,end):
global tree
psum = 0
while start<=end:
if start %2==1:
psum+=tree[start]
start+=1
if end %2==0:
psum+=tree[end]
end-=1
start=start//2
end = end//2
return psum
for i in range(n):
tree[startIndex+i]=int(input())
i=treeSize
while i != 1:
tree[i//2]+=tree[i]
i=i-1
for i in range(chnage+sum):
t , a , b = map(int,input().split())
if t ==1:
a=a+startIndex-1
change_node(a,b)
if t ==2:
a=a+startIndex-1
b=b+startIndex-1
print(subnet_sum(a,b))
최솟값찾기2(10868)
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.
여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.
현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.
이제 리프 노드의 개수는 1개이다.
- 입력
첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.
- 입출력 예시
10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10
--------------
5
38
20
5
해결책
- 세그먼트트리(최솟값전용) 생성하기
이문제는 위의 세그먼트를 이용하지만, 합에대한 세그먼트트리가 아닌 최솟값에대한 세그먼트 트리를 구현해주면된다. 리스트의 모든 초깃값에 대해서 sys.maxsize로 초기화시켜주고, 누적대신에 최솟값일시 해당인덱스의 값을 변경해주는 식으로 초기 트리를 구성해준다.
- 구간 최솟값 찾기
start≤end의 조건하에서
start%2==1이면
최솟값인지 확인하고, start+=1
end%2==0이면
최솟값인지 확인하고, end-=1
start/=2
end/=2
코드
import sys
input = sys.stdin.readline
n,question = map(int,input().split())
treeSize=1
tmp=n
while tmp!=0:
tmp=tmp//2
treeSize *=2
treeSize=treeSize * 2
startIndex = treeSize//2
tree = [sys.maxsize] * (treeSize+1)
def change_node(a,value):
global tree
dif=value-tree[a]
while a>0:
tree[a]+=dif
a=a//2
def find_min(start,end):
global tree
pmin=sys.maxsize
while start<=end:
if start %2==1:
pmin=min(pmin,tree[start])
start+=1
if end %2==0:
pmin=min(pmin,tree[end])
end-=1
start=start//2
end = end//2
return pmin
for i in range(n):
tree[startIndex+i]=int(input())
i=treeSize
while i != 1:
tree[i//2]=min(tree[i//2],tree[i])
i=i-1
for i in range(question):
a , b = map(int,input().split())
a=a+startIndex-1
b=b+startIndex-1
print(find_min(a,b))
댓글남기기