Dev_Diary

https://www.acmicpc.net/problem/2357세그먼트 트리 문제입니다.세그먼트 트리를 이용해 부분합을 구할 때 처럼 범위를 나누어 해당 범위의 부분적인 최소 / 최댓값을 구해 점차적으로 병합하며 큰 범위의 최소 / 최댓값을 구해주면 됩니다.import sysinput = sys.stdin.readline# 세그먼트 트리class SegTree: def __init__(self, nums): # 정수 리스트 self.nums = nums # 세그먼트 트리 self.segtree = [[] for _ in range(len(nums)*4)] self.partision_segtree(1, 0, len(nums)-1) ..

https://www.acmicpc.net/problem/2042제목만 보면 부분합 알고리즘을 사용할 것 같지만 어떻게 보면 비슷한 세그먼트 트리 기본 문제입니다.세그먼트 트리는 부분합과 비슷한 부분이 있습니다. 바로 부분의 값을 미리 계산해 놓고 필요할 때 적은 계산만으로 값을 도출하는 방법이라는 점 입니다. 다만 세그먼트 트리는 중간에 수를 바꾸는 등의 작업도 보다 빠르게 할 수 있어 좀 더 유연하게 사용할 수 있다는 장점이 있습니다. 기초 세그먼트 트리는 모습은 이진트리와 유사하며 각 노드는 해당하는 범위의 합 / 곱 등 사용자가 원하는 선형 계산의 값을 보유합니다. 또 각 노드의 자식 노드의 범위는 부모 노드의 범위의 절반씩에 해당합니다.또한 세그먼트 트리의 루트 노드는 1 로 설정하는 편이 편합..