[Algorithm] 펜윅 트리, 이진 인덱스 트리, BIT(Binary Indexed Tree)로 구간 합 문제 해결
어떤 배열의 특정 범위에 해당하는 수의 합을 구할 때 부분 합을 사용한다. 이 부분 합의 전처리 과정의 시간 복잡도는 O(N)이고 원하는 값을 구할 때의 시간 복잡도는 O(1)이다. 전처리 과정 sum[ i ]의 값을 arr의 인덱스 0부터 인덱스 i 까지의 합이라고 정의하고 아래와 같은 배열이 있다고 하자. sum[0]은 1일 것이고 sum[1]은 9일 것이고 sum[2]는 12일 것이다. 이를 구하는 과정을 파이썬을 나타내면 다음과 같고 시간 복잡도는 O(N)이다. arr=[1, 8, 3, 4, 6, 7, 4, 4] sum=[0 for _ in range(8)] sum[0]=arr[0] for i in range(1, 8): sum[i]=sum[i-1]+arr[i] 원하는 값 구하기 그런데 위 sum..
2023. 4. 23.
