Leta Learns

세그먼트 트리 예제 공부하고 나서 푸니까 금방 풀렸다. 다른 문제들도 풀어보고 싶긴 한데 어차피 못 풀 것 같다... 너무 어려운 문제는 고르지 말아야지.. 이게 과연 푸는 의미가 있는가.... import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def init(start, end, index): if start == end: tree[index] = num[start] return tree[index] mid = (start + end) // 2 tree[index] = init(start, mid, index*2) + init(mid+1, end, index*2+1) return tree[index] def partial_sum(st..

Segment Tree : 사용자가 요청한 쿼리에 대해서 더 빠르게 응답하기 위해 만들어진 자료구조. 특정 기준으로 트리를 전처리하여 연산 속도를 높이게 된다. 이진 트리 구조. 구간 트리라고도 불림. 배열로 구현 가능. 세그먼트 트리를 이루는 각 노드의 왼쪽 자식과 오른쪽 자식이 각각 해당 구간의 왼쪽 반과 오른쪽 반을 표현. => 이진 트리 구조 Segment Tree를 사용하는 이유 배열 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 있는 경우. arr[4] + arr[5] + arr[6] 의 부분합을 구하는 쿼리와 arr[4]의 값을 바꾸는 쿼리가 있다고 하면 보통의 방식에서 부분합을 구하는 쿼리는 O(N), 값을 바꾸는 쿼리는 O(1)의 시간복잡도를 요구한다. 이처럼 수..