https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net https://growth-coder.tistory.com/162 이전 포스팅에서 펜윅 트리(BIT, 이진 인덱스 트리)의 사용법에 대해서 공부하였다. 이 펜윅 트리를 사용하면 구간 합 문제를 쉽게 구현할 수 있다. 우선 갱신 함수이다. def update(i, num): arr[i]+=num while i0: res+=tree[i] i-..

어떤 배열의 특정 범위에 해당하는 수의 합을 구할 때 부분 합을 사용한다. 이 부분 합의 전처리 과정의 시간 복잡도는 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..