알고리즘 - Prefix Sum

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<bool> answerQueries(vector<int>& nums, vector<vector<int>>& queries, int limit) {
    vector<int> prefix = {nums[0]};
    for (int i = 1; i < nums.size(); i++) {
        prefix.push_back(prefix.back() + nums[i]);
    }
    
    vector<bool> ans;
    for (vector<int>& query: queries) {
        int x = query[0], y = query[1];
        int curr = prefix[y] - prefix[x] + nums[x];
        ans.push_back(curr < limit);
    }
    
    return ans;
}