Prefix Sum 배열에서 i 번째 까지의 값의 합을 가지고 있는 새로운 배열 prefix sum 배열을 만드는 것을 pre-processing이라고 볼 수 있고 main 로직에서 시간 복잡도를 줄여주는 역할을 한다. i ~ j 까지 합을 O(1)에 구할 수 있음 prefix[j] - prefix[i - 1] // 0이하로 out of bound되는 것을 막고 싶다면 prefix[j] - prefix[i] + nums[i] prefix sum 만들기 prefix sum이 없다면 query를 수행하는데 O(n) 만큼이 들고 query의 갯수가 m개라면 총 O(n*m) prefix sum을 사용함으로서 O(n + m)으로 시간복잡도를 낮출 수 있음.(O(n) 만큼의 공간을 추가 사용) vector answ..