题记：前缀和是一个比较重要的算法，我们如何使用他，什么时候使用它，在本篇做了一些小的总结，是在本人（蒟蒻）做题过程中的一个总结，供大家分享，因为我看python实现的好像不怎么多，我就使用python作为展示了。能力有限，有错误是难免的，还请大家包含。

前缀和（一维，二维，结合哈希表）

前缀和是编程中最基础也最核心的预处理技巧，本质是「空间换时间」，把频繁的区间求和操作从 O(n) 优化到 O(1)，尤其适合需要多次查询区间和的场景。

1. 基础概念

对于一个数组 nums，它的前缀和数组prefix 满足：

prefix[0]=0

prefix[i]=nums[0]+nums[1]+…+nums[i−1]

（注：前缀和数组通常从下标 0 开始，prefix[i] 表示「原数组前 i 个元素的和」，这样的设计能避免边界处理的麻烦）

2. 直观例子

比如原数组 nums = [11, 45, 14, 19]，对应的前缀和数组：

• prefix[0] = 0（前 0 个元素的和，空和）
• prefix[1] = 11（前 1 个元素：11）
• prefix[2] = 11+45 = 56（前 2 个元素）
• prefix[3] = 11+45+14 = 70（前 3 个元素）
• prefix[4] = 11+45+14+19 = 89（前 4 个元素）

前缀和的核心价值是O (1) 计算任意区间的和，这也是它能优化时间复杂度的关键。

1. 区间和公式

对于原数组中「从第 l 个元素到第 r 个元素」的区间（闭区间，下标从 0 开始），其和为：

sum(l,r)=prefix[r+1]−prefix[l]

2. 例子验证

比如求 nums[1] ~ nums[2]（45+14）的和：

• l=1，r=2
• sum = prefix [3] - prefix [1] = 70 - 11 = 59（45+14=59，正确）

再比如求 nums[0] ~ nums[3] 的和：

• sum = prefix [4] - prefix [0] = 89 - 0 = 89（正确）

实现的模板：

def build_prefix_sum(nums):
    n = len(nums)
    # 前缀和数组长度为n+1，初始值全0
    prefix = [0] * (n + 1)#创建的全零列表
    for i in range(1, n+1):
        # 核心递推公式：前i个元素和 = 前i-1个元素和 + 第i个元素（nums[i-1]）
        prefix[i] = prefix[i-1] + nums[i-1]
    return prefix

# 测试
nums = [11, 45, 14, 19]
prefix = build_prefix_sum(nums)
print(prefix)  # 输出 [0, 11, 56, 70, 89]

# 求区间和的函数
def get_range_sum(prefix, l, r):
    #1.是以数组的下标作为标定，从0开始 l: 原数组起始下标，r: 原数组结束下标（闭区间）
    return prefix[r+1] - prefix[l]
    #2.是以直观的展现为标定，从1开始，l：左起的数，r：右边界（闭区间）
    return perfix[r] - prefix[l-1]
    
# 测试：nums[1]~nums[2]的和
print(get_range_sum(prefix, 1, 2))  # 输出 59

2. 关键细节说明

• 前缀和数组长度为 n+1：用 prefix[0] = 0 作为哨兵，避免计算区间和时出现 l=0 需特殊处理的情况；
• 下标对应关系：原数组 nums[i-1] 对应前缀和数组 prefix[i]（因为 prefix[i] 是前 i 个元素的和）；
• 时间 / 空间复杂度：构建前缀和数组的时间复杂度是 O(n)，空间复杂度是 O(n)（可以优化为原地修改，但可读性差，不推荐）。

例题：（前缀和与枚举的结合）

P8830 [传智杯 #3 练习赛] 评委打分

题目描述

小 A 参加一个综艺节目。一共有 $n(3\le n\le 10^6)$ 名评委参与打分（分数范围是 0 到 100 的整数），每个评委依次亮出自己的得分。

为了节目效果，要求从第三个评委开始，每当第 $i$ 个评委给出打分后，立刻计算出出这个选手在前 $i$ 名评委的打分中，去掉一个最高分和一个最低分，剩下 $i-2$ 个评委的平均分，保留 $2$ 位小数。

输入格式

第一行输入一个整数 $n$，表示评委人数。

第二行输出 $n$ 个整数，表示各个评委的打分。

输出格式

输出共 $n-2$ 行，每行表示对应的答案。

输入输出样例 #1

输入 #1

6
11 45 14 19 19 81

输出 #1

14.00
16.50
17.33
24.25

题解：（80分，有点硬解了）

import sys

def main():
    # 读取输入（处理1e6数据时，sys.stdin更快）
    input = sys.stdin.read().split()
    n = int(input[0])
    scores = list(map(int, input[1:n+1]))
    res = []
    
    # 预处理前缀最大值、前缀最小值、前缀和
    prefix_sum = [0] * (n + 1)    # prefix_sum[i] = 前i个分数的和
    prefix_max = [0] * (n + 1)    # prefix_max[i] = 前i个分数的最大值
    prefix_min = [101] * (n + 1)  # prefix_min[i] = 前i个分数的最小值（初始值>100）
    
    for i in range(1, n+1):
        prefix_sum[i] = prefix_sum[i-1] + scores[i-1]
        prefix_max[i] = max(prefix_max[i-1], scores[i-1])
        prefix_min[i] = min(prefix_min[i-1], scores[i-1])
    
    for i in range(3, n+1):
        total = prefix_sum[i]         
        max_v = prefix_max[i]         
        min_v = prefix_min[i]        
        avg = (total - max_v - min_v) / (i - 2)
        res.append(f"{avg:.2f}") 
    print('\n'.join(res))
        

if __name__ == "__main__":
    main()

二维矩阵的前缀和：获得子区间矩阵的和：

一、核心原理（由浅入深）

先回顾一维前缀和：pre_sum[i] = pre_sum[i-1] + nums[i-1]，能快速求 [l..r] 的和。

矩阵前缀和的核心是：

1. 定义 pre_sum 矩阵，其中 pre_sum[i][j] 表示从原矩阵左上角 (0,0) 到 (i-1,j-1) 的子矩阵的和（注意：通常让 pre_sum 多一行一列，避免处理边界）。

2. 推导递推公式：pre_sum[i][j] = 原矩阵[i-1][j-1] + pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]（减去重复计算的部分）。

3. 任意子矩阵求和：若要求原矩阵中从 (x1,y1) 到 (x2,y2) 的和，公式为：

   sum = pre_sum[x2+1][y2+1] - pre_sum[x1][y2+1] - pre_sum[x2+1][y1] + pre_sum[x1][y1]
   

   。

二、Python 完整实现（含详细注释）

下面通过一个具体例子，展示矩阵前缀和的构建和查询全过程：

def matrix_prefix_sum(matrix):
    """
    构建矩阵的前缀和数组，并提供子矩阵求和功能
    :param matrix: 原始二维矩阵（非空）
    :return: 前缀和矩阵, 子矩阵求和函数
    """
    # 1. 获取矩阵的行数和列数
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    
    # 2. 初始化前缀和矩阵（多一行一列，初始值为0，避免边界判断）
    pre_sum = [[0]*(cols+1) for _ in range(rows+1)]
    
    # 3. 填充前缀和矩阵（核心递推）
    for i in range(1, rows+1):
        for j in range(1, cols+1):
            # 递推公式：当前值 = 原矩阵值 + 上方和 + 左方和 - 重复计算的左上角和
            pre_sum[i][j] = matrix[i-1][j-1] + pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]
    
    # 4. 定义子矩阵求和函数（封装查询逻辑）
    def get_submatrix_sum(x1, y1, x2, y2):
        """
        求原矩阵中从 (x1,y1) 到 (x2,y2) 的子矩阵和（闭区间）
        :param x1: 子矩阵左上角行号（从0开始）
        :param y1: 子矩阵左上角列号（从0开始）
        :param x2: 子矩阵右下角行号（从0开始）
        :param y2: 子矩阵右下角列号（从0开始）
        :return: 子矩阵的和
        """
        # 边界校验（可选，增强鲁棒性）
        if x1 < 0 or y1 < 0 or x2 >= rows or y2 >= cols or x1 > x2 or y1 > y2:
            raise ValueError("子矩阵坐标超出范围或不合法")
        # 查询公式
        return pre_sum[x2+1][y2+1] - pre_sum[x1][y2+1] - pre_sum[x2+1][y1] + pre_sum[x1][y1]
    
    return pre_sum, get_submatrix_sum

# ------------------- 测试示例 -------------------
if __name__ == "__main__":
    # 原始矩阵（3行4列）
    matrix = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]
    ]
    
    # 构建前缀和矩阵，并获取查询函数
    pre_sum, get_sum = matrix_prefix_sum(matrix)
    
    # 打印前缀和矩阵（直观查看）
    print("前缀和矩阵：")
    for row in pre_sum:
        print(row)
    
    # 测试1：求整个矩阵的和（0,0)到(2,3)
    print("\n整个矩阵的和：", get_sum(0, 0, 2, 3))  # 预期：78
    
    # 测试2：求第二行到第三行，第二列到第三列的和（1,1)到(2,2)
    print("子矩阵(1,1)-(2,2)的和：", get_sum(1, 1, 2, 2))  # 6+7+10+11=34
    
    # 测试3：求单个元素(0,2)的和
    print("单个元素(0,2)的和：", get_sum(0, 2, 0, 2))  # 预期：3

三、代码关键部分解释

1. 前缀和矩阵初始化：

   pre_sum = [[0]*(cols+1) for _ in range(rows+1)]

   让 pre_sum 比原矩阵多一行一列（行 / 列从 1 开始），避免处理 i=0 或 j=0 时的边界错误（比如 pre_sum[-1][j] 这种非法索引）。

2. 递推公式详解：

   pre_sum[i][j] = matrix[i-1][j-1] + pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]

   • matrix[i-1][j-1]：原矩阵当前位置的值；
   • pre_sum[i-1][j]：上方子矩阵的和；
   • pre_sum[i][j-1]：左方子矩阵的和；
   • pre_sum[i-1][j-1]：左上角子矩阵被重复加了两次，需要减去一次。

3. 子矩阵查询公式：

   pre_sum[x2+1][y2+1] - pre_sum[x1][y2+1] - pre_sum[x2+1][y1] + pre_sum[x1][y1]

   • pre_sum[x2+1][y2+1]：整个大矩阵 (0,0) 到 (x2,y2) 的和；
   • 减去 pre_sum[x1][y2+1]：去掉 (x1,0) 上方的部分；
   • 减去 pre_sum[x2+1][y1]：去掉 (0,y1) 左方的部分；
   • 加上 pre_sum[x1][y1]：因为左上角的部分被减了两次，需要补回来。

四、使用场景与注意事项

• 适用场景：需要多次查询不同子矩阵和的场景（如力扣「304. 二维区域和检索 - 矩阵不可变」），预处理 O(rows×cols)，查询 O(1)，远优于暴力枚举 O(rows×cols) 每次查询。
• 注意事项：
  1. 原矩阵坐标从 0 开始，前缀和矩阵从 1 开始，务必对应好；
  2. 若原矩阵有负数，公式依然成立（前缀和本身支持负数）；
  3. 若需要修改原矩阵，前缀和矩阵需要重新计算（适合静态矩阵）。

总结

1. 矩阵前缀和的核心是预处理辅助矩阵，通过递推公式避免重复计算，实现子矩阵和的快速查询；
2. 关键公式：构建时 pre_sum[i][j] = 原矩阵值 + 上 + 左 - 左上，查询时 sum = 大 - 上 - 左 + 左上；
3. 工程中建议给前缀和矩阵多一行一列，简化边界处理，同时增加坐标合法性校验提升鲁棒性。

例题：

P1387 最大正方形

题目描述

在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

保证矩阵里有至少一个 $1$。

输入格式

输入文件第一行为两个整数 $n,m(1\le n,m\le 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

输出格式

一个整数，最大正方形的边长。

输入输出样例 #1

输入 #1

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

输出 #1

2

题解：

import os
import sys

# 请在此输入您的代码
data = list(map(int,sys.stdin.read().split()))
ptr = 0
n = data[ptr]
m = data[ptr+1]
ptr += 2

max_res = 1

matrix = [[0]*(m) for _ in range(n)]
for i in range(n):
  for j in range (m):
    matrix[i][j] = data[ptr]
    ptr += 1
sum_1 = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range (1,m+1):
    sum_1[i][j] = matrix[i-1][j-1]+sum_1[i-1][j]+sum_1[i][j-1]-sum_1[i-1][j-1]
for i in range(n):
  for j in range(m):
    if matrix[i][j]==0:
      continue
    max_res_2 = min(n-i,m-j)
    for k in range(max_res_2,0,-1):
      x1,y1 = i,j
      x2,y2 = i+k-1,j+k-1
      sq_sum = sum_1[x2+1][y2+1]-sum_1[x1][y2+1]-sum_1[x2+1][y1]+sum_1[x1][y1]
      if sq_sum == k*k:
        if k > max_res:
          max_res = k
        break
print(max_res)

结合哈希表的前缀和相关内容（区间和是某个数的倍数，获取区间的数量/最大区间）：

关键洞察：利用哈希表存储前缀和出现的次数，将"寻找子数组"转化为"寻找配对"。

P3131 [USACO16JAN] Subsequences Summing to Sevens S

题目描述

Farmer John 的 $N$ 头奶牛站成一排，这是它们时不时会做的事情。每头奶牛都有一个独特的整数 ID 编号，以便 Farmer John 能够区分它们。Farmer John 希望为一组连续的奶牛拍照，但由于童年时与数字 $1\dots 6$ 相关的创伤事件，他只希望拍摄一组奶牛，如果它们的 ID 加起来是 7 的倍数。

请帮助 Farmer John 确定他可以拍摄的最大奶牛组的大小。

输入格式

输入的第一行包含 $N$（$1\le N\le 50,000$）。接下来的 $N$ 行每行包含一头奶牛的整数 ID（所有 ID 都在 $0\dots 1,000,000$ 范围内）。

输出格式

请输出 ID 之和为 7 的倍数的最大连续奶牛组中的奶牛数量。如果不存在这样的组，则输出 0。

输入输出样例 #1

输入 #1

7
3
5
1
6
2
14
10

输出 #1

5

说明/提示

在这个例子中，$5+1+6+2+14=28$。

一般的直接使用前缀和求解会超时:(双循环时间复杂度是O(n*n))

import sys
import math
import os

data = list(map(int,sys.stdin.read().split()))

n = data[0]
k = data[1]
num = data[2:2+n]
res = 0
prefix = [0]*(n+1)
for i in range(1,n+1):
  prefix[i] = prefix[i-1]+num[i-1]
for l in range(n):
  for r in range(l,n):
    sum_1 = prefix[r+1]-prefix[l]
    if (sum_1 % k == 0):
      res += 1
print(res)

这种类型的往往需要使用哈希表进行存储

哈希表将时间复杂度转换为空间复杂度O(n)->O(1)类似于字典的存储形式，

题目约束 n ≤ ?
│
├── n ≤ 5000 ──→ 暴力 O(n²) 可接受（C++可能，Python可能超时）
│ 但哈希表 O(n) 更保险
│
├── n ≤ 20000 ──→ C++ 暴力可能通过，Python 必须用哈希表
│
└── n ≥ 50000 ──→ 任何语言都必须用哈希表 O(n)

一、哈希表的用途（先明确目标）

• Key：前缀和模 7 的余数（只能是 0,1,2,3,4,5,6）
• Value：这个余数第一次出现时对应的前缀和下标
• 目标：后面再遇到相同余数时，用 “当前下标 − 第一次下标” 得到区间长度，求最大。

---

二、哈希表的创建：初始化

# 创建并初始化哈希表（字典）
first_occur = {0: 0}

1. 为什么一开始就放 {0: 0}？

• 0（key）：前缀和 prefix[0] = 0，它的余数是 0

• 0（value）：这个余数 0 第一次出现在前缀和下标 0

• 意义：

  用来处理 “从数组开头到当前位置，整个前缀和就是 7 的倍数” 这种情况。

  比如

  prefix[i] %7 = 0
  

  ，则长度 =

  i − 0 = i
  

2. 这是 “创建” 的关键一步

• 一开始哈希表不是空的，必须先放入这个初始状态；
• 后续只在 “余数没出现过” 时，才往表里加新键值对。

---

三、哈希表的更新规则（创建后的维护）

遍历数组，维护当前前缀和，计算余数 mod：

1. 如果 mod 已经在哈希表中：

   • 不修改哈希表（保证存的始终是第一次出现的下标，才能得到最长长度）
   • 只用它算长度：i - first_occur[mod]

2. 如果 mod 不在哈希表中：

   • 往哈希表里新增一条记录：

     first_occur[mod] = i
     

   • 这里的 i 是当前前缀和的下标（从 1 开始）。

---

对照样例：完整看哈希表从创建到填满的过程

样例：

n = 7

数组：[3,5,1,6,2,14,10]

前缀和下标：i = 0~7

• prefix[0] = 0
• prefix[1] = 3
• prefix[2] = 8
• prefix[3] = 9
• prefix[4] = 15
• prefix[5] = 17
• prefix[6] = 31
• prefix[7] = 41

哈希表创建 / 更新全过程：

1. 初始创建

   plaintext

   first_occur = {0:0}
   

2. i=1, mod=3

   3 不在表中 → 新增：

   plaintext

   first_occur = {0:0, 3:1}
   

3. i=2, mod=1

   1 不在表中 → 新增：

   plaintext

   first_occur = {0:0, 3:1, 1:2}
   

4. i=3, mod=2

   2 不在表中 → 新增：

   plaintext

   first_occur = {0:0, 3:1, 1:2, 2:3}
   

5. i=4, mod=1

   1 已存在 → 不更新哈希表

6. i=5, mod=3

   3 已存在 → 不更新哈希表

7. i=6, mod=3

   3 已存在 → 不更新哈希表

8. i=7, mod=6

   6 不在表中 → 新增：

   plaintex

   first_occur = {0:0, 3:1, 1:2, 2:3, 6:7}
   

最终哈希表：

{
    0: 0,
    1: 2,
    2: 3,
    3: 1,
    6: 7
}

• 余数 4、5 始终没出现，所以表里没有。

---

五、哈希表创建 / 使用的核心原则

1. 只在第一次遇到余数时插入

   • 保证 value 是最早的下标，才能算出最长区间。
   • 绝对不能重复覆盖，否则长度会变小。

2. Key 空间极小

   • 模 7 → 只有 0~6 共 7 种可能；
   • 哈希表最多存 7 条记录，空间复杂度 O (1)。

3. 创建分两步

   1. 初始：{0:0}
   2. 遍历：遇到新余数就 哈希表[余数] = 当前前缀和下标

4. 查询 O (1)

   • 判断余数是否在表中：if mod in first_occur
   • 取第一次下标：first_occur[mod]

---

六、代码对应的 “哈希表创建” 片段

# 1. 创建并初始化
first_occur = {0: 0}
max_len = 0
prefix = 0

for i in range(1, n+1):
    prefix += ids[i-1]
    mod = prefix % 7
    
    if mod in first_occur:
        # 已存在：只算长度，不改表
        current_len = i - first_occur[mod]
        max_len = max(max_len, current_len)
    else:
        # 2. 动态扩展哈希表：第一次出现，新增键值
        first_occur[mod] = i

---

七、总结一句话

• 哈希表一开始创建时就放入 {0:0}；
• 遍历过程中，只给第一次出现的余数设置记录；
• 已经有的余数，坚决不修改，保证存的是最早位置，用来求最长区间。

下面这个例题是差不多的道理，给大家参考练习

例2：（前缀和与哈希表结合2）

P8649 [蓝桥杯 2017 省 B] k 倍区间

题目描述

给定一个长度为 $N$ 的数列，$A_1,A_2,\cdots A_N$，如果其中一段连续的子序列 $A_i,A_{i+1},\cdots A_j(i\le j)$ 之和是 $K$ 的倍数，我们就称这个区间 $[i,j]$ 是 $K$ 倍区间。

你能求出数列中总共有多少个 $K$ 倍区间吗？

输入格式

第一行包含两个整数 $N$ 和 $K$ $(1\le N,K\le 10^5)$。

以下 $N$ 行每行包含一个整数 $A_i$ $(1\le A_i\le 10^5)$。

输出格式

输出一个整数，代表 $K$ 倍区间的数目。

输入输出样例 #1

输入 #1

5 2
1  
2  
3  
4  
5  

输出 #1

6

说明/提示

时限 2 秒, 256M。蓝桥杯 2017 年第八届

来csdn2年了，第一篇博客，惭愧惭愧。一切伟大源于一个微小的开始，一起加油！