Chương 19 - Prefix Sum

Prefix Sum = P[i] = arr[0] + arr[1] + ... + arr[i-1]. Cho phép tính tổng subarray [l, r] trong O(1): P[r+1] - P[l]. Đây là gateway cho Chương 6.4 (Subarray Sum K) và rất nhiều bài liên quan đến tổng / số dư / đếm subarray theo điều kiện. Cũng là nền cho Fenwick Tree (Chương 22).

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Convention P[0] = 0 để tổng [l, r] = P[r+1] - P[l].
  • Pattern prefix sum + hash đếm subarray theo điều kiện.
  • Prefix sum 2D với inclusion-exclusion.
  • Khi mảng có update → chuyển sang Fenwick / Segment (Ch 22).

Khi nào dùng pattern này?

  • Bài đếm / tổng subarray với điều kiện.
  • Range sum query - đặc biệt khi mảng immutable (mảng động thì dùng Fenwick).
  • Mở rộng lên 2D (Range Sum Query 2D, Chương 19.4).
  • Pattern “prefix sum mod K” để đếm subarray chia hết.

Template code 

# 1) Prefix sum 1D
P = [0] * (n + 1)
for i in range(n):
    P[i + 1] = P[i] + arr[i]

# Tổng arr[l..r] (inclusive):
sum_lr = P[r + 1] - P[l]


# 2) Prefix sum + hash đếm subarray = K (Subarray Sum K)
from collections import defaultdict
def count_subarray_sum_k(arr, k):
    counts = defaultdict(int)
    counts[0] = 1
    cur = result = 0
    for x in arr:
        cur += x
        result += counts[cur - k]
        counts[cur] += 1
    return result


# 3) Prefix sum 2D
P = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
    for c in range(cols):
        P[r+1][c+1] = mat[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
# Tổng rect (r1, c1) → (r2, c2):
# P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Bài tự luyện cuối chương

  • LC 525 - Contiguous Array
  • LC 974 - Subarray Sums Divisible by K
  • LC 1248 - Count Number of Nice Subarrays
  • LC 1314 - Matrix Block Sum
  • LC 1352 - Product of the Last K Numbers
  • LC 1769 - Minimum Number of Operations to Move All Balls to Each Box
  • LC 1989 - Maximum Number of People That Can Be Caught in Tag

19.1 Range Sum Query - Immutable (LC 303)

Đề bài

Thiết kế class: - NumArray(nums): khởi tạo với mảng số.

  • sumRange(left, right): trả về tổng nums[left..right] (inclusive).

Mảng không thay đổi sau khởi tạo. Yêu cầu sumRange chạy O(1).

Ví dụ 

Input (LC-style operation arrays):
  ops  = ["NumArray",            "sumRange", "sumRange", "sumRange"]
  args = [[[-2, 0, 3, -5, 2, -1]], [0, 2],     [2, 5],     [0, 5]]

Output: [null, 1, -1, -3]

Giải thích:
  NumArray([-2, 0, 3, -5, 2, -1])  → null  (khởi tạo prefix sum nội bộ)
  sumRange(0, 2)                   → 1      (-2 + 0 + 3)
  sumRange(2, 5)                   → -1     (3 + (-5) + 2 + (-1))
  sumRange(0, 5)                   → -3     (tổng toàn mảng)

Ràng buộc

  • 1 <= len(nums) <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= left <= right < len(nums)

Clarifying questions

  • Mảng có update không? → Không (theo đề Immutable; xem LC 307 cho Mutable).
  • Query với left > right? → Theo đề: left <= right.

Hướng tiếp cận

Precompute prefix sum trong __init__. Mỗi query O(1).

Code Python 3 

from typing import List

class NumArray:
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.P = [0] * (n + 1)
        for i in range(n):
            self.P[i + 1] = self.P[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.P[right + 1] - self.P[left]

Phân tích độ phức tạp

  • Init: O(n). Query: O(1). Bộ nhớ: O(n).

Bình luận

  • Convention P[0] = 0 là idiom - giúp công thức P[r+1] - P[l] không phải special-case l == 0.
  • Khi mảng có thể update → dùng Fenwick / Segment Tree (Chương 22).

Bài tự luyện liên quan

  • LC 307 - Range Sum Query - Mutable.
  • LC 304 - Range Sum Query 2D (bài 19.4).

19.2 Subarray Sum Equals K (LC 560) - recap

Đã giải đầy đủ ở Chương 6.4. Pattern: prefix sum + hash đếm cur - k.

Code Python 3 

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        counts = defaultdict(int)
        counts[0] = 1
        cur = result = 0
        for x in nums:
            cur += x
            result += counts[cur - k]
            counts[cur] += 1
        return result

Liên hệ với các bài khác

  • LC 974 - Subarray Sums Divisible by K: key = cur % k.
  • LC 525 - Contiguous Array (đếm 0=1): thay 0 → -1, key = cur.
  • LC 1248 - Count Number of Nice Subarrays: prefix sum của parity.

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(n) cho hash map.

Bài tự luyện liên quan

  • LC 974 - Subarray Sums Divisible by K.
  • LC 525 - Contiguous Array.

19.3 Continuous Subarray Sum (LC 523)

Đề bài

Cho mảng nums và số k. Trả về True nếu tồn tại subarray độ dài ≥ 2 có tổng là bội số của k (kể cả 0×k = 0).

Ví dụ 

Input:  nums = [23, 2, 4, 6, 7], k = 6   → True
Giải thích: [2, 4] có tổng 6 = 1*6.

Input:  nums = [23, 2, 6, 4, 7], k = 6   → True
Giải thích: [23, 2, 6, 4, 7] = 42 = 7*6.

Input:  nums = [1, 2, 3], k = 5          → False

Ràng buộc

  • 1 <= len(nums) <= 10^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= 2^31-1

Clarifying questions

  • n = 1? → Subarray length ≥ 2 nên trả False.
  • k = 0? → Cần subarray tổng = 0.

Hướng tiếp cận

Prefix sum mod K + hash.

Subarray nums[l..r] có tổng chia hết k ↔︎ P[r+1] % k == P[l] % k. Tìm 2 vị trí cùng modulo, khoảng cách ≥ 2.

Dict {remainder: earliest_index}. Với mỗi i, tính cur % k: - Nếu đã thấy remainder này trước đó tại j và i - j >= 2 → True. - Nếu chưa thấy → ghi i.

Code Python 3 

from typing import List

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # remainder -> earliest index where this prefix-sum remainder appeared.
        # Khởi tạo {0: -1} để cover trường hợp subarray bắt đầu từ index 0.
        first_idx: dict[int, int] = {0: -1}
        cur = 0
        for i, x in enumerate(nums):
            cur += x
            rem = cur % k
            if rem in first_idx:
                if i - first_idx[rem] >= 2:
                    return True
            else:
                first_idx[rem] = i
        return False

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(min(n, k)).

Bình luận

  • Tại sao chỉ lưu earliest? Vì ta muốn i - j lớn nhất (≥ 2) → giữ j nhỏ nhất là an toàn.
  • Bẫy {0: -1}: nếu prefix sum chính nó chia hết k và đủ dài (i ≥ 1) → match.

Bài tự luyện liên quan

  • LC 974 - Subarray Sums Divisible by K.
  • LC 525 - Contiguous Array.

19.4 Range Sum Query 2D - Immutable (LC 304)

Đề bài

Thiết kế class NumMatrix(matrix) với phương thức sumRegion(row1, col1, row2, col2) trả tổng vùng chữ nhật bao quanh bởi 4 góc (row1, col1) và (row2, col2) (inclusive cả hai đầu) trong O(1).

Ví dụ 

Input (LC-style operation arrays):
  ops  = ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
  args = [[[[3,0,1,4,2],
            [5,6,3,2,1],
            [1,2,0,1,5],
            [4,1,0,1,7],
            [1,0,3,0,5]]],
          [2, 1, 4, 3],
          [1, 1, 2, 2],
          [1, 2, 2, 4]]

Output: [null, 8, 11, 12]

Giải thích:
  NumMatrix(matrix)          → khởi tạo, return null
  sumRegion(2, 1, 4, 3)      → tổng vùng [2..4] × [1..3] = 8
  sumRegion(1, 1, 2, 2)      → tổng vùng [1..2] × [1..2] = 11
  sumRegion(1, 2, 2, 4)      → tổng vùng [1..2] × [2..4] = 12

Ràng buộc

  • 1 <= m, n <= 200
  • -10^4 <= matrix[i][j] <= 10^4

Clarifying questions

  • Matrix rỗng? → Constructor xử lý sẵn; query trả 0.
  • Query với r1 > r2? → Theo đề: r1 ≤ r2, c1 ≤ c2.

Hướng tiếp cận

Prefix sum 2D: P[r+1][c+1] = tổng vùng [0,0] → [r,c].

Inclusion-exclusion để lấy tổng vùng [r1,c1] → [r2,c2]:

P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]

Hình minh hoạ:

P[r2+1][c2+1] = tổng cả vùng (0,0) đến (r2,c2)
  − P[r1][c2+1] = trừ phần trên (0,0) đến (r1-1, c2)
  − P[r2+1][c1] = trừ phần trái (0,0) đến (r2, c1-1)
  + P[r1][c1]  = cộng lại phần overlap đã trừ 2 lần

Code Python 3 

from typing import List

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            return
        rows, cols = len(matrix), len(matrix[0])
        self.P = [[0] * (cols + 1) for _ in range(rows + 1)]
        for r in range(rows):
            for c in range(cols):
                self.P[r + 1][c + 1] = (
                    matrix[r][c]
                    + self.P[r][c + 1]
                    + self.P[r + 1][c]
                    - self.P[r][c]
                )

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (
            self.P[row2 + 1][col2 + 1]
            - self.P[row1][col2 + 1]
            - self.P[row2 + 1][col1]
            + self.P[row1][col1]
        )

Phân tích độ phức tạp

  • Init: O(rows · cols). Query: O(1). Bộ nhớ: O(rows · cols).

Bình luận

  • Inclusion-exclusion là tinh thần Combinatorics - sẽ tái xuất ở Chương 44.
  • Khi matrix có update → 2D Fenwick Tree.

Bài tự luyện liên quan

  • LC 308 - Range Sum Query 2D Mutable.
  • LC 363 - Max Sum of Rectangle No Larger Than K.
  • LC 1314 - Matrix Block Sum.

19.5 Product of Array Except Self (LC 238) - recap

Đã giải đầy đủ ở Chương 1.3. Liên hệ với prefix sum.

Code Python 3 

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n
        left = 1
        for i in range(n):
            result[i] = left
            left *= nums[i]
        right = 1
        for i in range(n - 1, -1, -1):
            result[i] *= right
            right *= nums[i]
        return result

Liên hệ pattern

  • Bài này dùng prefix product thay vì prefix sum (left) và suffix product (right).
  • Khác với prefix-sum thuần: không cần P[0] = 1 riêng vì left = 1 ban đầu đảm nhận vai trò “phần tử trung lập”.
  • Cùng tinh thần “prefix + suffix” - pattern xuất hiện ở:
    • LC 42 - Trapping Rain Water (prefix max + suffix max).
    • LC 152 - Maximum Product Subarray (prefix max/min).
    • LC 135 - Candy (Chương 16).

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(1) extra (không tính output).

Bài tự luyện liên quan

  • LC 152 - Maximum Product Subarray.
  • LC 42 - Trapping Rain Water.

19.6 Find Pivot Index (LC 724)

Đề bài

Cho nums. Tìm pivot index - chỉ số i mà tổng nums[0..i-1] == nums[i+1..n-1]. Trả index trái nhất, hoặc -1.

Ví dụ 

Input:  nums = [1, 7, 3, 6, 5, 6]
Output: 3
Giải thích: tổng trái 1+7+3=11; tổng phải 5+6=11.

Input:  nums = [1, 2, 3]   → -1
Input:  nums = [2, 1, -1]  → 0    (trái = rỗng = 0; phải = 1 + -1 = 0)

Ràng buộc

  • 1 <= len(nums) <= 10^4
  • -1000 <= nums[i] <= 1000

Clarifying questions

  • Multiple pivot index? → Trả index trái nhất (theo đề LC).

Hướng tiếp cận

left[i] + nums[i] + right[i] = total. Pivot ↔︎ left[i] == right[i] ↔︎ left[i] = (total - nums[i]) / 2.

1 lượt: giữ left_sum. Tại i: pivot ↔︎ left_sum == total - left_sum - nums[i].

Code Python 3 

from typing import List

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left_sum = 0
        for i, x in enumerate(nums):
            if left_sum == total - left_sum - x:
                return i
            left_sum += x
        return -1

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Edge case i = 0 hoặc i = n - 1: trái/phải có thể rỗng → tổng 0. Code trên xử lý tự nhiên.

Bài tự luyện liên quan

  • LC 1991 - Find the Middle Index in Array.
  • LC 1314 - Matrix Block Sum.

Tóm tắt chương & Quyết định

P[0] = 0 - vì sao 

arr:  [ a0, a1, a2, a3 ]
P:    [  0, a0, a0+a1, a0+a1+a2, a0+a1+a2+a3 ]
       P[0] P[1] P[2]   P[3]      P[4]

Tổng arr[l..r] (đóng, 0-index) = P[r+1] - P[l]. Nếu thiếu P[0] = 0, công thức cần case riêng cho l == 0.

Continuous Subarray Sum (LC 523) - distance condition

  • Cần subarray có độ dài ≥ 2 với tổng % k == 0.
  • Khi 2 prefix có cùng prefix % k, độ dài subarray giữa chúng = j - i. Yêu cầu j - i ≥ 2.
  • Lưu chỉ index đầu tiên xuất hiện modulo đó.

Modulo với số âm

Python % luôn trả [0, k): (-3) % 5 == 2. An toàn cho prefix mod. Java/C++: (-3) % 5 == -3 → cần ((x % k) + k) % k.

Product Except Self recap

Đã có code đầy đủ ở Chương 1.3. Recap ở đây nhấn mạnh: prefix product và suffix product, không dùng P[r+1] - P[l] mà là nhân, nên không cần P[0] = 1 riêng - code dùng left = 1, right = 1 ban đầu.