一、核心概念与原理在算法与工程开发中，前缀和与差分是一对互补的基础算法工具，专门解决区间查询与区间修改两大高频问题。前缀和：通过预处理，将区间和查询从暴力 O (n) 优化至 O (1)。差分：通过增量记录，将区间批量修改从暴力 O (n) 优化至 O (1)。两者互为逆运算，搭配使用可实现「多次修改 + 多次查询」的高效流程，是处理数组、矩阵问题的「黄金组合」。二、一维前缀和与一维差分2.1 一维前缀和定义给定原数组a[1...n]，前缀和数组s[i]表示从第一个元素到第 i 个元素的累加和：s[i]=a[1]+a[2]+⋯+a[i]递推公式s[i]=s[i−1]+a[i]含义：当前前缀和 = 前一项前缀和 + 当前元素。区间查询求区间[l, r]内所有元素的和：sum(l,r)=s[r]−s[l−1]完整代码#include iostream using namespace std; const int N = 100010; int a[N], s[N]; int main() { int n; cin n; // 输入原数组 for (int i = 1; i = n; i++) cin a[i]; // 构建前缀和数组 for (int i = 1; i = n; i++) s[i] = s[i-1] + a[i]; // 区间查询示例 int l, r; cin l r; cout s[r] - s[l-1] endl; return 0; }2.2 一维差分定义差分数组d[i]记录相邻元素的增量：d[1]=a[1],d[i]=a[i]−a[i−1](i1)核心性
前缀和与差分 完整学习笔记
发布时间：2026/6/6 12:48:10
一、核心概念与原理在算法与工程开发中，前缀和与差分是一对互补的基础算法工具，专门解决区间查询与区间修改两大高频问题。前缀和：通过预处理，将区间和查询从暴力 O (n) 优化至 O (1)。差分：通过增量记录，将区间批量修改从暴力 O (n) 优化至 O (1)。两者互为逆运算，搭配使用可实现「多次修改 + 多次查询」的高效流程，是处理数组、矩阵问题的「黄金组合」。二、一维前缀和与一维差分2.1 一维前缀和定义给定原数组a[1...n]，前缀和数组s[i]表示从第一个元素到第 i 个元素的累加和：s[i]=a[1]+a[2]+⋯+a[i]递推公式s[i]=s[i−1]+a[i]含义：当前前缀和 = 前一项前缀和 + 当前元素。区间查询求区间[l, r]内所有元素的和：sum(l,r)=s[r]−s[l−1]完整代码#include iostream using namespace std; const int N = 100010; int a[N], s[N]; int main() { int n; cin n; // 输入原数组 for (int i = 1; i = n; i++) cin a[i]; // 构建前缀和数组 for (int i = 1; i = n; i++) s[i] = s[i-1] + a[i]; // 区间查询示例 int l, r; cin l r; cout s[r] - s[l-1] endl; return 0; }2.2 一维差分定义差分数组d[i]记录相邻元素的增量：d[1]=a[1],d[i]=a[i]−a[i−1](i1)核心性
第四章——set方法为属性赋值)
