#prefix-sum
노트 2개
Algorithm › Data Structure
세그먼트 트리배열을 구간별로 나눠 각 구간의 합·최솟값 같은 요약을 이진 트리에 저장해, 값이 바뀌는 배열에서도 구간 질의와 갱신을 모두 O(log n)에 처리하는 자료구조. 배열 크기 잡기, 재귀 구현, 지연 전파와 펜윅 트리 비교까지 정리한다.
Algorithm
구간 합과 접두사 합앞에서부터의 누적 합을 미리 구해 두고, 임의 구간의 합을 뺄셈 한 번으로 구하는 기법. 접미사·곱 변형과 해시를 곁들여 합이 k인 부분 배열을 세는 방법.