누적합

누적합 (Prefix sum)누적합은 주어진 배열의 각 원소에 대해 그 원소를 포함하여 이전 모든 원소의 합을 계산한 값을 저장하는 알고리즘특정구간의 원소의 연산을 여러번 하는 일반적인 경우,  지정된 인덱스부터 하나씩 더했을 때, 총 O(n^2) 가 소요됨.누적합의 경우, 누적합 배열이 준비된 후 연산하면 배열의 크기에 비례하므로 시간복잡도가 총 O(n)배열이 크거나 연산을 많이 실행할 경우에 자주 쓰임  1. 1차원 배열 누적합ex) 자연수의 누적합index01234arr12345prefix_sum1361015 arr[i] = prefix_sum[i] - prefix_sum[i-1] [BOJ] 태상이의 훈련소생활[19951번] - https://www.acmicpc.net/problem/19951ex..