[알고리즘] 누적 합, 구간 합 Prefix Sum

누적 합 Prefix Sum

배열에서 구간 합을 구해야 하는 문제에서 중첩 for 문을 사용해 값을 계속 더해주면 O(n^2) 시간 만큼 걸리지만

누적 합을 사용하면 계속 더해줄 필요 없이 마이너스 연산 만으로 해결 가능하다. O(1)

 

동적 계획법 문제들에서 DP로 연산 결과를 저장할 때에도 누적 합 방식이 많이 사용되는 듯 하다. 

 

* prefixsum 만들 때 index 0 말고 1부터 담아야 만들기 쉬움

psum

1, ~2, ~3, ~4 … 

 

suffix sum 은 뒤에서 부터 더하는 것. 알고리즘 대회 같은데서 가끔 나오긴 하는데 코테에서는 잘 안나옴.

 

구간쿼리 구할 때 

배열의 요소가 정적일 경우 psum 

동적일 경우 펜윅트리(?) 

 

1차원 배열일 때 누적 합 구하는 건 간단하지만

2차원 배열은 좀,, 복잡하긴 했다. 

코드가 좀 길어지긴 하지만 이것도 방법만 알면 구현이 크게 어렵진 않은 듯. 

 

누적 합 문제들

1차원 배열

- 

2차원 배열

-