前缀和与差分：区间求和、批量修改与二维容斥

一、暴力求和的痛点与前缀和降维

场景：给出一个数组 $a$ ，每次询问一段区间 $[l, r]$ 内所有数字的总和。

暴力解法 ( $O(N)$ )：每次收到一个询问，写一个 for 循环从 $l$ 遍历到 $r$ 累加。如果数组长度为 10 万，询问也有 10 万次，总计算量高达 $10^{10}$ ，必然超时。

物理劣势：我们一直在重复计算。比如刚刚算过 $[1, 5]$ 的和，现在要算 $[1, 6]$ 的和，明明只差了一个数字，暴力解法却要把前 5 个数字全部重新加一遍。

1. 前缀和：提前打包的智慧

为了不重复劳动，我们可以花一点时间做一个“预处理”。定义一个新数组 $s$ ，其中 $s[i]$ 表示从数组第 1 个元素一直加到第 $i$ 个元素的总和。这就像是把前面所有的数字“打包”成了一个结果。

它的递推式极其简单：

s[i] = s[i-1] + a[i]

（前

i

个数字的和 = 前

i-1

个数字的和 + 第

i

个数字本身）

直观例子：假设原数组 a = [3, -2, 5, 1, 4]。为了防止边界越界，我们让数组下标从 1 开始，并且强制规定 $s[0] = 0$ 。

$s[1] = s[0] + 3 = 3$
$s[2] = s[1] + (-2) = 1$
$s[3] = s[2] + 5 = 6$
$s[4] = s[3] + 1 = 7$
$s[5] = s[4] + 4 = 11$ 最终得到的前缀和数组为 s = [0, 3, 1, 6, 7, 11]。

2. $O(1)$ 的区间查询：为什么是 `l-1`？

有了前缀和数组，怎么快速求任意区间 $[l, r]$ 的和呢？答案就是“大包减去小包”： $s[r] - s[l-1]$ 。

💡 【实战检验】

查 [2, 4]：我们想要第 2 到第 4 个数字的和。用 $s[4]$ （前4个数的总和）减去谁呢？我们想保留第 2 个数字，所以只能把排在它前面的第 1 个数字减掉，也就是减去 $s[1]$ 。 $s[4] - s[1] = 7 - 3 = 4$ 。核对原数组： $-2 + 5 + 1 = 4$ ，正确！

查 [1, 5]：保留第 1 个数字，减去 $s[0]$ 。 $s[5] - s[0] = 11 - 0 = 11$ 。

查 [3, 3]：也就是查第 3 个数字本身。 $s[3] - s[2] = 6 - 1 = 5$ 。

3. 静态区间求和模板实现

输入约定：第一行读入 $n$ 和查询次数 $q$ ( $1 \le n, q \le 200000$ )，接着读入 $n$ 个原数组元素（数值绝对值不超过 $10^9$ ）。最后 $q$ 行，每行给出询问区间 $l$ 和 $r$ ，每问输出一行结果。 复杂度分析：预处理 $O(n)$ ，每次查询 $O(1)$ 。总时间 $O(n+q)$ ，空间 $O(n)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

int a[N],s[N];
int n,q;

void solve(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		// 边读入边计算前缀和，s[0] 默认为 0
		s[i]=s[i-1]+a[i];
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		// O(1) 回答查询
		cout<<s[r]-s[l-1]<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

二、一维差分：化批量区间加为两点修改

场景：给出一个数组 $a$ ，每次要求把区间 $[l, r]$ 里的每一个数字都加上一个值 $c$ 。

暴力解法 ( $O(N)$ )：写一个循环把 $[l, r]$ 挨个加一遍。在海量修改面前依然会被卡死。

1. 差分数组的诞生：只记录变化

如果我们不关心每个位置具体是多少，只关心当前元素比前一个元素多了多少，就可以引入差分数组 $d$ 。定义 $d[i] = a[i] - a[i-1]$ 。

直观例子：依然是 a = [3, -2, 5, 1, 4]。（假设 $a[0]=0$ ）

$d[1] = 3 - 0 = 3$
$d[2] = -2 - 3 = -5$
$d[3] = 5 - (-2) = 7$
$d[4] = 1 - 5 = -4$
$d[5] = 4 - 1 = 3$ 得到差分数组 d = [3, -5, 7, -4, 3]。

2. 区间修改的降维打击

现在我们要给区间 $[l, r]$ 整体加 $c$ 。你会发现：在 $l$ 到 $r$ 内部，因为大家同时涨了 $c$ ，所以它们彼此之间的“落差”（差分值）并没有改变！发生改变的只有两个边界：

第 $l$ 个数字涨了，但它前面的 $l-1$ 没涨，所以落差拉大：d[l] += c
第 $r+1$ 个数字没涨，但前面的 $r$ 涨了，所以落差缩小：d[r+1] -= c

原本要修改 $r-l+1$ 个数字，现在只需要 $O(1)$ 修改两个端点！这就是差分的核心魔法。

3. 前缀和与差分的逆向关系：原物奉还

当你做完所有乱七八糟的修改后，怎么把原数组还原出来呢？ 差分数组的前缀和，就是原数组。 因为 $a[i] = a[i-1] + d[i]$ ，这刚好就是前缀和的定义。前缀和与差分是一对完美的逆运算，就像微积分一样。

💡 【实战推演】 我们接着用刚才的 d = [3, -5, 7, -4, 3] 演示两次操作：

操作 1：给 [2, 4] 加 3。

d[2] += 3 变成 -2；d[5] -= 3 变成 0。

此时差分数组：[3, -2, 7, -4, 0]。

如果现在求一遍前缀和还原，原数组变成：[3, 1, 8, 4, 4]。

操作 2：继续给 [3, 5] 减 2（即加 -2）。

针对当前的差分数组：d[3] += -2 变成 5；d[6] -= -2 变成 2（注意越界一位没关系，开够数组即可）。

此时差分数组：[3, -2, 5, -4, 0]（以及 d[6]=2）。

最终求一遍前缀和还原：[3, 1, 6, 2, 2]。完美对应了两次操作后的结果！

图中只记录本次修改的增量，差分增量累加后为[0,3,3,3,0]，与原数组逐项相加才是修改后的[3,1,8,4,4]。数组（3,-2,5,1,4）的区间（2,4）和为7−3=4；同一区间加3，只在差分增量的第2格加3、第5格减3，累加后增量为（0,3,3,3,0）。

4. 一维批量区间加模板实现

输入约定：第一行读入 $n$ 和修改次数 $m$ ( $1 \le n \le 200000$ ， $0 \le m \le 200000$ )，接着读入原数组。随后 $m$ 行，每行给出修改区间 $l,r$ 和增量 $c$ （原值与增量绝对值不超过 $10^9$ ）。最后输出修改完成的整个数组。 复杂度分析：每次修改 $O(1)$ ，最后还原 $O(n)$ 。总时间 $O(n+m)$ ，空间 $O(n)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

int a[N],d[N];
int n,m;

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		// 构建初始差分
		d[i]=a[i]-a[i-1];
	}
	
	// 接收海量修改操作，O(1) 打标记
	while(m--){
		int l,r,c;
		cin>>l>>r>>c;
		d[l]+=c;
		d[r+1]-=c;
	}
	
	// 所有修改结束后，扫一遍前缀和还原
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+d[i]; 
		cout<<a[i]<<(i==n?"":" ");
	}
	cout<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

三、二维的进阶：容斥原理的重叠抵消

把一维的思想升维到矩阵上，核心逻辑变成了“左边+上边-左上角”。

1. 二维前缀和

$s[i][j]$ 的物理意义：以 $(1,1)$ 为左上角， $(i,j)$ 为右下角的矩形内的所有元素之和。

递推方程：一块拼图由它左边的拼图、上面的拼图和它自己组成。但左上角被加了两次，必须减去一次。 s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

查询区间 $(x_1, y_1)$ 到 $(x_2, y_2)$ ：大矩形减去上面的长条和左边的长条。由于左上角被减了两次，要再加回来。 ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

💡 【矩形推演】 原矩阵：第一行 1 2 3，第二行 4 5 6。按照递推方程，得到的二维前缀和有效部分为：第一行 1 3 6 第二行 5 12 21

2. 二维差分

在二维空间里，给一个矩形区域加一个数字，只会引起四个角的落差变化。如果你给左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 统一加上 $c$ ：

d[x1][y1] += c：整个右下大区域都被加上了 $c$ 。
d[x2+1][y1] -= c：下方的越界区域本不该加，减去。
d[x1][y2+1] -= c：右侧的越界区域本不该加，减去。
d[x2+1][y2+1] += c：右下角的越界区域被减了两次，补回来。

💡 【批量修改与查询推演】 接着刚才的矩阵。现在我们给“两行中的第2、3列全部加10”。这相当于给左上角 (1, 2) 到右下角 (2, 3) 的矩形加 10。修改并还原后，矩阵变为：第一行 1 12 13 第二行 4 15 16

用新前缀和验证：整矩阵总和变成了 $1+12+13+4+15+16 = 61$ 。如果只查修改过的第2、3列： $12+13+15+16 = 56$ 。一切吻合！

3. 二维批量修改后查询模板实现

输入约定：第一行读入行数 $n$ 、列数 $m$ 、修改次数 $u$ 、查询次数 $q$ ( $1 \le n,m \le 1000$ ， $0 \le u,q \le 200000$ 。修改与查询均可为0)。接着读入 $n \times m$ 的原矩阵（原值与增量绝对值不超过 $10^6$ ）。随后 $u$ 行依次是每次修改的 $x_1, y_1, x_2, y_2, c$ ，最后 $q$ 行是查询的 $x_1, y_1, x_2, y_2$ 。全部修改完成后输出每次查询结果。 复杂度分析：总时间 $O(n \times m + u + q)$ ，空间 $O(n \times m)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;

int a[N][N],d[N][N],s[N][N];
int n,m,u,q;

void solve(){
	cin>>n>>m>>u>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			// 初始化构建二维差分
			d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
		}
	}
	
	// O(1) 批量修改四角
	while(u--){
		int x1,y1,x2,y2,c;
		cin>>x1>>y1>>x2>>y2>>c;
		d[x1][y1]+=c;
		d[x2+1][y1]-=c;
		d[x1][y2+1]-=c;
		d[x2+1][y2+1]+=c;
	}
	
	// O(n*m) 统一还原并计算新前缀和
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			// 差分做前缀和得到原数组，暂存回 a 矩阵
			a[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
			// 针对新数组再做一次前缀和，用来响应最后的查询
			s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
		}
	}
	
	// O(1) 响应矩阵和查询
	while(q--){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		int ans=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
		cout<<ans<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

四、视角的升维：贡献法求所有子段和

如果题目要求计算所有可能非空子段的总和，直接暴力累加是 $O(N^3)$ ，哪怕用了前缀和去枚举两端点，依然会被卡在 $O(N^2)$ 。此时我们需要跳出区间视角的限制，转为元素视角，这就是传说中的“贡献法”。

核心问题：对于数组中的某一个数 $a[i]$ ，它在所有的子段中，到底出现了多少次？

我们知道，一个子段由左端点和右端点决定。要让子段包含 $a[i]$ ，那么：

左端点的选择可以是： $1, 2, \dots, i$ 。一共 $i$ 种选择。
右端点的选择可以是： $i, i+1, \dots, n$ 。一共 $n-i+1$ 种选择。所以包含 $a[i]$ 的子段总数就是 $i \times (n-i+1)$ 。它对总和的贡献就是 $a[i] \times i \times (n-i+1)$ 。

💡 【实战推演】 原数组 a = [2, -1, 3]，长度 $n=3$ 。

a[1] = 2 的出现次数： $1 \times (3-1+1) = 3$ 次。（被包含在 [2], [2,-1], [2,-1,3] 中）

a[2] = -1 的出现次数： $2 \times (3-2+1) = 4$ 次。（包含于 [2,-1], [2,-1,3], [-1], [-1,3]）

a[3] = 3 的出现次数： $3 \times (3-3+1) = 3$ 次。（包含于 [2,-1,3], [-1,3], [3]）

总贡献 = $2 \times 3 + (-1) \times 4 + 3 \times 3 = 6 - 4 + 9 = 11$ 。暴力枚举这 6 个子段的和： $2 + 1 + 4 - 1 + 2 + 3 = 11$ 。完全一致，但我们把复杂度降到了 $O(N)$ ！

五、前缀异或：自反性下的无损抵消

1. 异或运算的物理特性与子段查询

除了加减法，位运算中的**按位异或（^，数学符号 $\oplus$ ）**同样是前缀思想的经典舞台。为什么前缀和能通过“大包减小包”求区间和？因为减法是加法的逆运算： $(A + B) - A = B$ 。而异或运算更加神奇——它的逆运算就是它自己：

任何数异或自己都归零： $x \oplus x = 0$ （自反性）
任何数异或 0 保持不变： $x \oplus 0 = x$ （幺元）

我们同样定义前缀异或数组 $s[i] = a[1] \oplus a[2] \oplus \dots \oplus a[i]$ ，递推关系为：

s[i] = s[i-1] \oplus a[i]

规定

s[0] = 0

。

当我们需要查询区间 $[l, r]$ 内所有元素的异或总和时，不需要写循环，直接计算：

\text{XOR}(l, r) = s[r] \oplus s[l-1]

为什么直接异或就能抵消？ 因为 $s[r] = (a[1] \oplus \dots \oplus a[l-1]) \oplus (a[l] \oplus \dots \oplus a[r]) = s[l-1] \oplus \text{XOR}(l, r)$ 。我们在等式两边同时异或 $s[l-1]$ ，根据自反性：

s[r] \oplus s[l-1] = s[l-1] \oplus s[l-1] \oplus \text{XOR}(l, r) = 0 \oplus \text{XOR}(l, r) = \text{XOR}(l, r)

多余的前缀部分

1 \dots l-1

就像被橡皮擦擦掉一样自动消失了！

💡 【手算检验】 设原数组 a = [3, 5, 2, 6]（二进制分别为 011, 101, 010, 110）。按照递推求前缀异或：

$s[0] = 0$

$s[1] = 0 \oplus 3 = 3$

$s[2] = 3 \oplus 5 = 6$

$s[3] = 6 \oplus 2 = 4$

$s[4] = 4 \oplus 6 = 2$ 得到 s = [0, 3, 6, 4, 2]。

现在查区间 $[2, 4]$ 的异或和： $s[4] \oplus s[1] = 2 \oplus 3 = 1$ 。手工验证原数组第 2 到 4 项： $5 \oplus 2 \oplus 6 = 7 \oplus 6 = 1$ 。一步到位！

2. 核心考法：子段异或和为 0 的等价转化

在很多赛题中，题目会问：“有多少个连续子段的异或和为 0？” 直接枚举左右端点是 $O(n^2)$ 。但借助前缀异或：

\text{XOR}(l, r) = 0 \iff s[r] \oplus s[l-1] = 0 \iff s[r] = s[l-1]

看懂这个式子，整个问题就瞬间降维了：“找一段异或和为 0 的子区间”，等价于“在前缀异或数组里找两个数值相同的位置”！ 我们只需要统计前缀异或数组中每个数字出现了多少次，如果某个数值出现了 $c$ 次，那么任意从中挑出两个位置都能配成一个异或和为 0 的区间，贡献就是 $\frac{c(c-1)}{2}$ 。别漏掉空前缀 $s[0]=0$ ，它也要计入，才能统计从第 1 个数开始的子段。

六、前缀和与频次统计：负数环境下的子段和计数

1. 为什么负数会让滑动窗口失效？

信奥赛中有一类极为高频的题目：“给出一个数组，求有多少个连续子段的和恰好等于 $k$ ”。很多同学第一反应是写双指针或者滑动窗口：右指针右移和变大，左指针右移和变小。但请大家立刻打住！如果原数组包含负数，区间右移和可能变小，左移和可能变大，单调性彻底破裂，滑动窗口就会完全抓瞎。

此时降维的唯一解药，依然是前缀和方程：

s[r] - s[l-1] = k

把未知量移到等号一侧：

s[l-1] = s[r] - k

这句话的物理意义非常漂亮：当我们从左到右枚举右端点 $r$ 时， $s[r]$ 和目标 $k$ 都是已经确定的常数。我们只需要知道，在当前位置之前，曾经出现过多少个前缀和恰好等于 $s[r] - k$ 的历史位置！

2. 状态设计与空前缀 $s[0]$ 的致命细节

我们一边遍历数组计算当前的前缀和 $s[r]$ ，一边用哈希表（或数组计数桶）cnt[val] 记录历史前缀和 val 出现的次数。

对于当前遍历到的位置 $r$ ：

查询前面有多少个合法的左端点：ans += cnt[s[r] - k]；
把当前的前缀和记入桶中：cnt[s[r]]++。

⚠️ 【考场避坑核心：为什么必须预先执行 cnt[0] = 1？】 十个初学者有九个会漏掉这行代码。请思考：假设原数组开头的第 1 个数本身就等于 $k$ ，那么子段 $[1, 1]$ 的和就是 $k$ ，这显然是一个合法解。此时 $r=1$ ， $s[1] = k$ 。我们要找的左端点前缀是 $s[l-1] = s[1] - k = 0$ 。这个 $s[0]=0$ 对应的是一个“什么数都不选的空前缀”。如果一开始没有把 cnt[0] 设为 1，程序就找不到这个合法的起点，所有从下标 1 开始的合法子段会被全部漏算！

💡 【手算推演】 数组 a = [1, -1, 1, 1, -1]，求和为 $k=1$ 的子段个数。初始：cnt[0] = 1，ans = 0。

$r=1, a[1]=1 \implies s[1]=1$ ：目标 $1-1=0$ ，cnt[0]=1，ans += 1（下标区间 [1,1]）；记录 cnt[1]=1。

$r=2, a[2]=-1 \implies s[2]=0$ ：目标 $0-1=-1$ ，cnt[-1]=0；记录 cnt[0]=2。

$r=3, a[3]=1 \implies s[3]=1$ ：目标 $1-1=0$ ，cnt[0]=2，ans += 2（下标区间 [1,3] 与 [3,3]）；记录 cnt[1]=2。

$r=4, a[4]=1 \implies s[4]=2$ ：目标 $2-1=1$ ，cnt[1]=2，ans += 2（下标区间 [2,4] 与 [4,4]）；记录 cnt[2]=1。

$r=5, a[5]=-1 \implies s[5]=1$ ：目标 $1-1=0$ ，cnt[0]=2，ans += 2（下标区间 [1,5] 与 [3,5]）；记录 cnt[1]=3。最终总数： $1 + 0 + 2 + 2 + 2 = 7$ 个。完全正确，时间复杂度只有 $O(n \log n)$ （用 map）或 $O(n)$ （用哈希表）。

3. 子段和为 k 计数完整实现

输入约定：第一行包含两个整数 $n, k$ （ $1 \le n \le 200000, -10^9 \le k \le 10^9$ ）。第二行包含 $n$ 个整数 $a_i$ （ $-10^9 \le a_i \le 10^9$ ）。 输出约定：输出一行一个整数，表示和为 $k$ 的连续子段总个数。 复杂度分析：时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;

int a[N],s[N];
int n,k;
map<int,int> cnt; // 前缀和数值范围很大且有负数，用 map 统计频次

void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	
	int ans=0;
	// 核心：空前缀 s[0]=0 预先出现了一次
	cnt[0]=1;
	
	for(int r=1;r<=n;r++){
		int target=s[r]-k;
		// 查前面有多少个合法的 l-1 使得 s[l-1] == target
		if(cnt.count(target)){
			ans+=cnt[target];
		}
		// 记录当前前缀和，供后面的右端点使用
		cnt[s[r]]++;
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

样例输入：

5 1
1 -1 1 1 -1

样例输出：

七、差分到在线树状数组的思维跨越（选学）

📌 【选学先修说明】 本小节属于进阶衔接内容。适合已经学过基础树状数组（Binary Indexed Tree / Fenwick Tree）单点修改与前缀查询的同学阅读。如果尚未接触树状数组，可先体会其中的思维转化路径。

1. 静态离线与动态在线的分水岭

差分数组最迷人的地方在于 $O(1)$ 端点打标记，但它有一个致命的阿喀琉斯之踵：它是纯静态、离线的。它的运行模式是：“一口气做完所有的 $m$ 次修改，最后花 $O(n)$ 统一扫一遍还原”。如果考题要求修改与查询交替进行——“区间加一个数，立刻查某处的数值，接着再区间加”，如果每次查都重新求一遍前缀和，总时间会直接飙升到 $O(m \times n)$ ，瞬间超时。

如何突破这个死穴？核心钥匙就是：把差分数组搬进树状数组里！

2. 映射一：差分思想驱动“区间加、单点查”

回忆差分的基本定义：差分数组 $d$ 的前缀和，恰好就是原数组的当前值：

a[x] = \sum_{i=1}^x d[i]

现在请对比两边的操作对应关系：

对原数组做区间修改 $[l, r]$ 加 $c$ ：在差分体系下，它只是两次单点修改： $d[l] += c$ 以及 $d[r+1] -= c$ 。
对原数组做单点查询 $a[x]$ ：在差分体系下，它本质上就是求差分数组 $d$ 的前缀和： $\sum_{i=1}^x d[i]$ 。

树状数组最擅长什么？树状数组天生就是用来做**“单点修改”和“前缀求和”的！因此，只要我们用一个树状数组去维护差分数组 $d$ **：

区间修改：调用 2 次树状数组的单点加（位置 $l$ 加 $c$ ，位置 $r+1$ 加 $-c$ ），单次耗时 $O(\log n)$ ；
单点查询：调用 1 次树状数组的前缀查询（查 $1 \dots x$ 的和），单次耗时 $O(\log n)$ 。原本无法承受的动态区间修改与查询，就这样被差分的物理意义轻松攻破！

// 依赖标准树状数组结构：void add(int x, int v) 与 int query(int x)
// 区间加：转化为差分数组的两次单点修改
void range_add(int l, int r, int c){
	add(l, c);
	add(r + 1, -c);
}
// 单点查：转化为差分数组的前缀求和
int point_query(int x){
	return query(x);
}

3. 映射二：两重前缀推导“区间加、区间查”

很多同学会进一步追问：如果不仅要动态区间加，还要动态查任意区间和 $\sum_{i=1}^x a[i]$ 呢？我们把原数组的前缀和用差分数组彻底展开：

\sum_{i=1}^x a[i] = \sum_{i=1}^x \sum_{j=1}^i d[j]

这是一块经典的三角形双重求和。让我们从每一个差分元素 $d[j]$ 的贡献视角来观察它被加了多少次：

$d[1]$ 存在于 $a[1], a[2], \dots, a[x]$ 中，一共被加了 $x$ 次；
$d[2]$ 存在于 $a[2], a[3], \dots, a[x]$ 中，一共被加了 $x-1$ 次；
通项规律： $d[j]$ （ $1 \le j \le x$ ）一共被累加了 $(x - j + 1)$ 次！

把这个次数代入式子中化简：

\sum_{i=1}^x a[i] = \sum_{j=1}^x d[j] \times (x - j + 1) = \sum_{j=1}^x \big((x + 1)d[j] - j \cdot d[j]\big)

提出外层常数

(x + 1)

：

\sum_{i=1}^x a[i] = (x + 1) \sum_{j=1}^x d[j] - \sum_{j=1}^x (j \cdot d[j])

极其震撼的结论诞生了：左边的 $\sum d[j]$ 是差分数组的前缀和；右边的 $\sum (j \cdot d[j])$ 是一个新序列 $j \cdot d[j]$ 的前缀和！

这意味着，我们只需要同时开两个树状数组：

树状数组 $C_1$ ：维护差分数组 $d[i]$ ；
树状数组 $C_2$ ：维护辅助数组 $i \cdot d[i]$ 。

每次区间加 $[l, r]$ 加 $c$ 时：

给 $C_1$ 维护：位置 $l$ 加上 $c$ ，位置 $r+1$ 加上 $-c$ ；
给 $C_2$ 维护：位置 $l$ 加上 $l \times c$ ，位置 $r+1$ 加上 $-(r+1) \times c$ 。

任意前缀和 $\sum_{i=1}^x a[i]$ 只需要一次计算：

\text{sum}(x) = (x + 1) \times \text{query}(C_1, x) - \text{query}(C_2, x)

区间和

\text{sum}(l, r)

依旧是

\text{sum}(r) - \text{sum}(l-1)

。每次操作依然是稳稳的

O(\log n)

！

这正是竞赛算法中最迷人的逻辑闭环：前缀和产生差分，差分又反哺前缀和，最终在高级数据结构里融为一体。

八、课堂练习与延伸

固定长度最大子段和 给出长度为 $n$ 的数组，求所有长度为 $k$ 的连续子段中和最大的是多少？（提示：注意全负数情况下的初始极小值设定，利用前缀和滑动比较）。
修改后最大格值与数量 给一个全 0 矩阵做若干次二维区间修改，求最后矩阵里最大的数字是多少，以及这个数字有几个？
所有子段总和 不限长度，求一维数组所有可能的子段和加起来是多少？（提示：直接默写上方的贡献法公式，注意数据范围防止乘法爆 long long）。

延伸思考：基础差分适合“先做完所有修改，再统一进行查询”。如果改成“修改一次，立刻查一次”的交替操作，每次还原重建就要耗费 $O(N)$ 。第七节已经给出了衔接办法：让树状数组动态维护差分及其前缀和。完整实现见《树状数组》，更一般的区间操作见《线段树》。

前缀和与差分