المجاميع البادئة والإجماليات التراكمية

مسألة مجموع النطاق

# Naive: O(n) per query
def range_sum_naive(nums, i, j):
    return sum(nums[i:j+1])

nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3))  # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4))  # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operations

بناء مصفوفة المجموع السابق

def build_prefix(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    return prefix

def range_sum(prefix, i, j):
    return prefix[j+1] - prefix[i]  # O(1)

nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre)                    # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3))  # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15  correct
print(range_sum(pre, 1, 3))  # 15

مجموع المصفوفة الجزئية يساوي K

from collections import defaultdict

def subarray_sum_k(nums, k):
    count = 0
    current = 0
    freq = defaultdict(int)
    freq[0] = 1  # empty prefix
    for n in nums:
        current += n
        count += freq[current - k]  # how many prior sums give diff=k
        freq[current] += 1
    return count

print(subarray_sum_k([1, 1, 1], 2))    # 2
print(subarray_sum_k([1, 2, 3], 3))    # 2  ([1,2] and [3])

أكبر مجموع لمصفوفة جزئية باستخدام المجموع السابق

def max_subarray_prefix(nums):
    max_sum  = float('-inf')
    min_pre  = 0  # prefix[0] = 0
    current  = 0
    for n in nums:
        current += n
        max_sum = max(max_sum, current - min_pre)
        min_pre = min(min_pre, current)
    return max_sum

print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6  (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1

المجاميع السابقة ثنائية الأبعاد لاستعلامات الشبكة

def build_2d_prefix(grid):
    R, C = len(grid), len(grid[0])
    P = [[0]*(C+1) for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            P[r][c] = (P[r-1][c] + P[r][c-1]
                       - P[r-1][c-1] + grid[r-1][c-1])
    return P

def rect_sum(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1))  # 3+0+5+6 = 14

المجموع التراكمي لفهرس التوازن

def find_pivot_index(nums):
    total = sum(nums)
    left_sum = 0
    for i, n in enumerate(nums):
        # right_sum = total - left_sum - nums[i]
        if left_sum == total - left_sum - n:
            return i
        left_sum += n
    return -1

print(find_pivot_index([1, 7, 3, 6, 5, 6]))  # 3
print(find_pivot_index([1, 2, 3]))             # -1

مصفوفة حاصل ضرب العناصر ما عدا العنصر نفسه

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    # Left pass: result[i] = product of nums[:i]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    # Right pass: multiply in product of nums[i+1:]
    suffix = 1
    for i in range(n-1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6]   O(n) time, O(1) extra space

المجموع السابق مع باقي القسمة

from collections import defaultdict

def subarray_div_by_k(nums, k):
    freq = defaultdict(int)
    freq[0] = 1
    current = 0
    count = 0
    for n in nums:
        current = (current + n) % k
        count += freq[current]
        freq[current] += 1
    return count

print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7  (seven subarrays divisible by 5)

مصفوفة الفروق لتحديثات النطاق

def apply_range_updates(n, updates):
    # updates: list of (l, r, val)
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l]   += val
        diff[r+1] -= val
    # Reconstruct with prefix sum
    result = []
    running = 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]

المجموع السابق في مسائل المقابلات

# Template: prefix sum + hash map for subarray problems
from collections import defaultdict

def subarray_count_template(nums, target):
    """
    Count subarrays with property involving prefix sums.
    Adapt 'target' and lookup condition for each problem.
    """
    freq = defaultdict(int)
    freq[0] = 1          # empty prefix at sum=0
    current = 0
    count = 0
    for n in nums:
        current += n
        count += freq[current - target]  # adjust per problem
        freq[current] += 1
    return count

print(subarray_count_template([1,2,3,2,1], 3))  # 3

المجموع التراكمي والقيمة العظمى التراكمية

def max_profit(prices):
    # Running minimum buy price
    min_price = float('inf')
    max_prof  = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_prof:
            max_prof = price - min_price
    return max_prof

def left_max_array(heights):
    # Running max from left for trapping rain water
    n = len(heights)
    left_max = [0] * n
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], heights[i])
    return left_max

print(max_profit([7,1,5,3,6,4]))  # 5

اختبار سريع

مراجعة الدرس