사실 Technique라고 하기도 뭐하지만... 최근에 여러문제들을 풀면서 느낀 점이 있어서 간단하게 적어 놓으려고 한다. Prefix Sum 이란? Prefix = 접미사 sum = 합. 그니까 앞에서 부터의 합을 의미한다. 어떠한 값이 들어있는 기존의 배열 arr이 존재한다고 하면 $pre[x]=\sum_{i=1}^{x} arr[i]$ 로 표현되는 값들이 prefix sum들이라는 것이다. How? prefix sum 배열을 채우는 것은 $O(N)$만에 정말 간단하게 할 수 있다. $pre[i]=pre[i-1]+arr[i]$ 로 할 수 있다. 어떤 식으로 활용해야 할지에 대해서 고민을 해봐야 한다. prefix sum은 구간 합을 구할 때 주로 사용되어진다. i부터 j까지의 구간합은 $pre[j]-p..