Python前缀和数组快速查询技巧

本文深入解析了Python中前缀和数组的核心实现技巧与常见陷阱，系统讲解了一维前缀和如何通过长度为n+1的数组高效支持O(1)区间求和查询（关键在于prefix[r+1]−prefix[l]的下标设计），以及二维前缀和如何借助容斥原理计算子矩阵和（必须多开行列、严格遵循加减顺序），同时强调避免浅拷贝、实时切片、numpy.cumsum误用等高频错误，并明确指出前缀和仅适用于静态数据+高频查询场景——一旦涉及修改，应果断转向树状数组或线段树。文末以LeetCode实战提示收束，直击算法面试中最易失分的边界细节与思维误区。

一维前缀和：用 list 累加构造，查询靠下标减法

一维前缀和本质是把「从开头到每个位置的累加值」存下来，后续查任意区间 [l, r] 的和就不用再循环加一遍。关键不是“怎么算”，而是“下标对不对”——多数人栽在边界上。

• prefix[i] 通常定义为 nums[0] + nums[1] + ... + nums[i-1]（即 prefix[0] = 0），这样 query(l, r) 就是 prefix[r+1] - prefix[l]，不用特判 l == 0
• 别用 prefix[i] = sum(nums[:i]) 实时切片求和——时间退化成 O(n²)，老老实实用一次遍历：

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

• 如果原数组下标从 1 开始（比如题目给的是 1-indexed 输入），别硬套 0-indexed 模板，先统一转成 0-indexed 再建前缀和，否则 l/r 映射错一位，结果全偏

二维前缀和：按行优先展开成二维 dp，容斥原理绕不开

二维前缀和不是“每行单独做一维”，而是把左上角 (0,0) 到当前点 (i,j) 的矩形和存下来。核心公式是：prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + matrix[i][j]。漏掉中间的减法，整个数组就溢出。

• 必须用 (i+1, j+1) 开辟多一行一列，让 prefix[0][*] 和 prefix[*][0] 全为 0，否则查 (0,0) 到 (r,c) 时要写一堆 if 判断
• 查子矩阵 [r1, c1] 到 [r2, c2]（闭区间）的和，公式固定为：prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]。记混加减顺序，结果必错；建议画个图，把四个角对应区域标出来再推
• 初始化二维 prefix 时别用 [[0] * (m+1)] * (n+1)——这是浅拷贝，改一行全变。老实用嵌套列表推导：[[0] * (m + 1) for _ in range(n + 1)]

修改频繁？前缀和就不该上场

前缀和只适合「静态数组 + 大量查询」场景。一旦有单点修改（比如 nums[i] += x），重算整个前缀和是 O(n) 或 O(nm)，比暴力还慢。

• 需要边改边查，直接换 fenwick tree（树状数组）或 segment tree（线段树）——它们单次修改+查询都是 O(log n)
• 真想硬用前缀和顶着改？那每次修改后必须调用完整重建函数，别只更新一个位置，否则后续所有查询都错
• LeetCode 上标“前缀和”的题，90% 不带修改；但看到“数据流”“在线查询”“update 方法”等字眼，立刻放弃前缀和思路

Python 实现注意：别用 numpy.cumsum 替代手写

numpy.cumsum 虽快，但它返回的是新数组，且默认展平多维数组。用它做二维前缀和，要么手动 reshape 再逐行处理，要么结果维度错乱，反而更难 debug。

• 纯 Python 场景下，手写循环比依赖 numpy 更可控、更符合算法题约束（很多 OJ 不开 numpy）
• 如果坚持用 numpy，二维必须指定 axis：np.cumsum(matrix, axis=0) 是列方向累加，axis=1 是行方向——但这只是“行/列前缀和”，不是真正的二维矩形前缀和
• 真正二维前缀和在 numpy 里没内置函数，硬写也得按容斥公式来，不如回归原生逻辑

实际写的时候，最常漏的是二维容斥里的那个加回项，或者一维 prefix 长度多开/少开 1。这些地方不画小例子跑两组数，光看公式根本记不住。

本篇关于《Python前缀和数组快速查询技巧》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！