고난이도 자료구조 세그먼트 트리 개념 이해하기 1편

1. 특정한 구간에 존재하는 모든 수의 합 어떤 수열이 주어질때, 만약 특정 구간 [a,b]에 존재하는 모든 수의 합을 구하라고 한다면 어떻게 구할 수 있을까? 가장 쉬운 방법은, 그냥 반복문으로 [a,b]까지 돌아서 모든 수의 누적합을 구하면 된다 answer = 0 for i in range(a,b+1): answer += A[i] 만약 배열 A의 크기가 N일때, 최악의 경우 위 코드의 시간 복잡도는 O(N)이다. 1번부터 N번까지 다 더하라하면 O(N)이니까 여기까지는 괜찮은데 만약 이러한 질문을 M번이나 한다면? O(N)의 연산을 M번 수행해야하므로, 시간복잡도는 O(NM)이고 N,M이 매우 크다면, 당연히 매우 느리다 2. Prefix sum 만약 S[0] = 0이고, 1번부터 i번까지의 수열 ..