Notice
Recent Posts
Recent Comments
Link
목록2023/04/13 (1)
HJW's IT Blog
Algorithm: 부분합(Prefix Sum)
부분합이란? 부분합은 배열의 각원소까지의 누적합을 계산한 배열을 말한다. 부분합 배열의 i 번째 원소는 원래 배열 의 1번째부터 i 번째 원소까지의 합을 나타낸다. Square Root Decomposition(전처리: O(n), 질의: O(sqrt(n)) 이 방법은 배열을 sqrt(n) 개의 블록으로 나누고 각 블록에 대한 누적합을 계산하여 저장한다. 예를 들어 배열 A = [1,2,3,4,5,6,7,8,9,10] 의 배열이 있다. 배열을 sqrt(n), 즉, 3개의 블록으로 나눈다면 다음과 같다 B[0] = A[0] + A[1] + A[2] -> 6 B[1] = A[3] + A[4] + A[5] ->15 B[2] = A[6] + A[7] + A[8] ->24 B[3] = A[9] -> 10 B = [..
알고리즘
2023. 4. 13. 08:55