구간 합Prifix Sum

Prifix Sum

• 주어진 구간의 합을 구하는 빠른 계산 방법
• main idea: 처음부터 n번째 원소까지의 연속된 총합
  
• prefix sum time complexity = O(n)
• pk = pk−1 + ak−1
  → 각각의 연속된 인덱스의 합(구간합)은 constant timeO(1)에 계산 가능
  
  

swift로 구현

func prefixSums(A: [Int], start: Int, end: Int) -> Int {
    // prefixSum 배열 만들기 O(n)
    let n = A.count
    var prefixSum = Array(repeating: A[0], count: n)
    
    for i in 1...n-1 {
        prefixSum[i] = prefixSum[i-1] + A[i]
    }
    
    // 구간합 구하기 O(1)
    let sumStartToEnd = prefixSum[end-1] - (start-1 == 0 ? 0 : prefixSum[start - 1])
    
    return sumStartToEnd
}

• prefixSum 만들고, 구간합 구하는 time complexity → O(n+m)

🔖 참고

• Codility: Chapter5.prefixSums.pdf