펜윅트리 (Fenwick Tree, Binary Indexed Tree, BIT)펜윅트리는 트리 구조를 1차원 배열로 구현한 자료구조로, 각 위치에서 특정 구간을 대표하는 값을 저장하여 빠르게 구간 합 등을 계산할 수 있다. 업데이트와 쿼리 연산의 시간 복잡도는 O(logN)이다. 1기반 인덱싱을 사용하기 때문에 배열의 크기를 N + 1 (N은 데이터의 크기)로 설정하는 경우가 많다. 세그먼트 트리보다 상대적으로 구현이 간단하고 메모리 사용량이 적다. 주요 연산 비교연산펜윅 트리세그먼트 트리구간 쿼리O(logN)O(logN)단일 업데이트O(logN)O(logN)구간 업데이트O(NlogN)O(logN) (Lazy Propagation 사용 시)메모리 사용량O(N)O(4 * N) 펜윅 트리 코드#inclu..
누적합 누적합은 리스트의 각 원소에 대해 그 이전 원소들의 합을 미리 구해 구간의 합을 구하는 방법이다. 이를테면 매출을 매일 기록해둔 카페 주인이 주말 매출과 주중 매출을 알고 싶어한다. 월요일을 일주일의 시작이라고 가정하고 예시를 살펴보자. 카페 수익 월 화 수 목 금 토 일 1 2 3 4 5 6 7 화요일부터 금요일까지의 수익은 2,3,4,5의 합인 14이다. 또 수요일부터 일요일까지의 매출의 합은 3,4,5,6,7의 합인 25가 된다. 데이터가 적으면 빠르게 구할 수 있지만, 데이터가 많아질수록 합을 구하는 시간이 오래 걸린다. 이때 누적합을 이용하면 빠르게 구할 수 있다. 화요일부터 금요일까지의 매출은 2,3,4,5를 다 더해주는 것이 아니라, 금요일까지의 누적합에서 월요일까지의 누적합을 빼주면..
코드 # 누적합: 리스트의 각 원소에 대해 그 이전 원소들의 합을 미리 구하는 방법 # n = 100000, nlogn 이하로 구하자 # sum 함수의 시간복잡도는 O(N), 긴 시퀀스를 구할 때는 시간이 오래걸린다. # 아래 방법은 O(N+M)으로 해결할 수 있다. import sys input = sys.stdin.readline n,m = map(int, input().split()) score = [*map(int, input().split())] temp = 0 arr = [0] # 제로인덱스임을 감안해서 0 추가 for i in score: temp += i # 구간합 arr.append(temp) for _ in range(m): x,y = map(int, input().split()) pr..
