前缀和与差分数组

import sys

nums = [int(x) for x in sys.stdin.read().strip().split(",")]   # 一行，逗号分隔
n = len(nums)
pre = [0] * (n + 1)                        # pre[i] = 前 i 个数之和；pre[0] = 0
for i in range(n):
    pre[i + 1] = pre[i] + nums[i]
total = pre[n]

ans = -1
for i in range(n):                         # 从左往右，第一个满足的就停
    left = pre[i]                          # 编号 i 之前所有数之和
    right = total - pre[i + 1]             # 编号 i 之后所有数之和（减去 pre[i+1] 才不含自己）
    if left == right:
        ans = i
        break
print(ans)

自测用例：题面两个示例，以及「7」「1,-1,0」「0,0,0」三组边界（第 04 节与第 09 节给了期望输出）。

import sys

data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
nums = [int(x) for x in data[2:2 + n]]

seen = {0}                                 # 空前缀的和是 0，余数 0 先进集合
pre = 0
found = 0
for x in nums:
    pre += x
    r = pre % m                            # Python 的 % 结果恒为非负
    if r in seen:                          # 之前出现过同样的余数 → 中间这一段的和是 m 的倍数
        found = 1
        break
    seen.add(r)
print(found)

自测用例：第 05 节三组手算例；再自己写一个 O(n²) 枚举全部连续段的暴力程序，在几组随机输入（含负数）上对拍。

import sys

data = sys.stdin.read().split()
n, target = int(data[0]), int(data[1])
nums = [int(x) for x in data[2:2 + n]]

total = n * (n + 1) // 2                   # 非空子数组总数
if target <= 0:                            # 元素非负：每个子数组的和都 ≥ 0 ≥ target，全部满足
    print(total)
else:
    fewer = 0                              # 和 < target 的子数组个数
    left = 0
    win = 0
    for right in range(n):
        win += nums[right]
        while win >= target:               # 收缩到窗口和 < target（元素非负保证窗口和单调）
            win -= nums[left]
            left += 1
        fewer += right - left + 1          # 以 right 结尾、和 < target 的子数组恰有这么多个
    print(total - fewer)

输入：第一行 n 和目标值 target，第二行 n 个非负整数；输出和 ≥ target 的连续子数组个数。自测用例：第 10 节练习 5 的两组手算与 3 0 / 1 2 3（target = 0 → 6）；再用 O(n²) 暴力枚举在几组随机输入上对拍。也可用前缀和 + 二分（第 10 节练习 5 答案里说明）。

def apply_range_adds(n, ops):
    diff = [0] * (n + 1)              # 多开一格，r+1 最大可以是 n
    for l, r, v in ops:               # 0 基闭区间 [l, r] 整体加 v
        diff[l] += v
        diff[r + 1] -= v
    out = []
    running = 0
    for i in range(n):                # 一次前缀累加恢复最终数组
        running += diff[i]
        out.append(running)
    return out

assert apply_range_adds(6, [(1, 3, 2), (2, 5, 1)]) == [0, 2, 3, 3, 1, 1]
assert apply_range_adds(3, [(0, 2, 5)]) == [5, 5, 5]          # 覆盖到最后一格：diff[3] -= 5 不越界
assert apply_range_adds(4, [(0, 0, 1), (3, 3, 1)]) == [1, 0, 0, 1]

diff 开 n + 1 长度，r = n − 1 时 diff[n] −= v 落在多开的那一格，恢复时只累加前 n 格。

def build_pre(a):
    pre = [0] * (len(a) + 1)          # 比原数组长一格，pre[0] = 0
    for i, x in enumerate(a):
        pre[i + 1] = pre[i] + x       # pre[i+1] = 前 i+1 项之和
    return pre

def range_sum(pre, l, r):
    return pre[r + 1] - pre[l]        # 0 基闭区间 [l, r]

pre = build_pre([1, 7, 3, 6, 5, 6])
assert pre == [0, 1, 8, 11, 17, 22, 28]
assert range_sum(pre, 0, 1) == 8      # 1 + 7（含首元素）
assert range_sum(pre, 3, 5) == 17     # 6 + 5 + 6（含尾元素）
assert range_sum(pre, 2, 2) == 3      # 单个元素

四条断言分别覆盖：整表、含首元素、含尾元素、单元素。