المصفوفات والمجاميع السابقة وعقود المجالات

def prefix_sums(values):
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix

def range_sum(prefix, left, right):
    n = len(prefix) - 1
    if not 0 <= left <= right <= n:
        raise ValueError("Invalid half-open range")
    return prefix[right] - prefix[left]

prefix = prefix_sums([4, -2, 5, 1])
print(prefix)
print(range_sum(prefix, 1, 3))
print(range_sum(prefix, 2, 2))

[0, 4, 2, 7, 8]
3
0

يشمل الاستعلام [1,3) القيمتين -2 و5. وعند تساوي الطرفين لا يُختار أي عنصر، فيكون الناتج صفرا.

def apply_additions(n, updates):
    diff = [0] * (n + 1)
    for left, right, delta in updates:
        if not 0 <= left <= right <= n:
            raise ValueError("Invalid half-open range")
        diff[left] += delta
        diff[right] -= delta
    result = []
    running = 0
    for index in range(n):
        running += diff[index]
        result.append(running)
    return result

print(apply_additions(5, [(1, 4, 3), (2, 5, -1)]))

[0, 3, 2, 2, -1]

يتداخل التحديث الثاني مع الموضعين 2 و3، ويمتد ليشمل الموضع 4. وتُسجّل نقطة التوقف عند 5، لكنها لا تُصدر عنصرا في الناتج.