[알고리즘] 누적합(Prefix Sum)

개념

일반적으로 누적합을 구함에 있어, i번째부터 j번째까지의 누적합을 구하라고 할 때마다 하나씩 더하면 i~j까지를 m개의 원소라고 하면 시간 복잡도가 m(j-i+1)의 제곱으로 늘어난다.
하지만 간단한 개념을 도입하면 시간복잡도를 O(2)까지 줄일 수 있다.

2042번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기

www.acmicpc.net

10986. 나머지 합

문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai +

l1m3kun.tistory.com