Prefix Sum 누적합 (영상처리에서 누적영상)

prefix sum(프리픽스 섬, 누적합)은 배열의 앞에서부터의 합을 미리 계산해서 저장해두는 것이에요.

---

🔸 예시로 설명할게요:

nums = [1, 2, 3, 4, 5]

 

이 배열의 prefix sum은 다음과 같아요:

prefix[0] = 1

prefix[1] = 1 + 2 = 3

prefix[2] = 1 + 2 + 3 = 6

prefix[3] = 1 + 2 + 3 + 4 = 10

prefix[4] = 1 + 2 + 3 + 4 + 5 = 15

즉, prefix = [1, 3, 6, 10, 15]

---

🔹 왜 쓰냐면?

예를 들어 nums[1] + nums[2] + nums[3] 이런 계산을 자주 해야 하면
매번 더하는 대신에 한 번에 구할 수 있어요:

prefix[3] - prefix[0] = 10 - 1 = 9

 

**시간 복잡도 O(1)**으로 빠르게 구할 수 있죠.

---

🔸 정리

• prefix sum = 누적합
• 구간 합을 빠르게 구하기 위해 미리 계산해둔 배열
• 처음에 계산은 O(n), 나중에 구간합은 O(1)

class PrefixSum:

    def __init__(self, nums):
        self.prefix = []
        total = 0
        for n in nums:
            total += n
            self.prefix.append(total)
        
    def rangeSum(self, left, right):
        preRight = self.prefix[right]
        preLeft = self.prefix[left - 1] if left > 0 else 0
        return (preRight - preLeft)