Blog

C# 前缀和与差分数组

作者

预处理一次，之后每个区间查询都是常数时间。还有一个几乎没人教的反向技巧：只写两个格子，就能给整个区间做一次更新。

第 2 篇的滑动窗口带着一个前提：窗口变大，量也必须跟着变大。只要出现一个负数，这个前提就不成立，整个模式随之失效。

前缀和不在乎这些。你先付一次成本，之后每个区间问题都只是一次减法。

下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里粘贴。

这笔交易

Console.WriteLine($"{"n",9}  {"queries",9}  {"scan each",16}  {"prefix",12}");

foreach ((int n, int q) in new[] { (10, 5), (1_000, 1_000), (200_000, 200_000) })
{
    long scan = (long)q * n;          // worst case: every query spans the array
    long prefix = n + q;              // build once, then O(1) per query
    Console.WriteLine($"{n,9:N0}  {q,9:N0}  {scan,16:N0}  {prefix,12:N0}");
}

输出：

        n    queries         scan each        prefix
       10          5                50            15
    1,000      1,000         1,000,000         2,000
  200,000    200,000    40,000,000,000       400,000

四百亿对四十万。本篇所有模式都是这个样子：先做一次线性的工作，之后每个问题 O(1) 回答。

模式 11 — 前缀和

pre[i] 存的是索引 i 之前所有元素的和。数组有 n+1 个格子，不是 n 个，多出来的那一个是有实际作用的。

a 3 1 4 1 5 9 2 6 01 23 45 67 a[2..5] = 19 pre 0 3 4 8 9 14 23 25 31 4 23 pre[i] 位于 a[i] 之前的边界上，不在 a[i] 上。所以 pre 有 n+1 个格子。 sum a[2..5] = pre[6] − pre[2] = 23 − 4 = 19

这个差一错误人人都要花一下午：pre 按边界编号，不按元素编号。pre[0] = 0 是空前缀，有了它，从索引 0 开始的区间不用特殊处理也能算对。

int[] a = [3, 1, 4, 1, 5, 9, 2, 6];

// pre[i] is the sum of the first i values, so pre[0] is 0 and pre.Length is n+1.
int[] pre = new int[a.Length + 1];
for (int i = 0; i < a.Length; i++) pre[i + 1] = pre[i] + a[i];

Console.WriteLine($"a   = [{string.Join(", ", a)}]");
Console.WriteLine($"pre = [{string.Join(", ", pre)}]");
Console.WriteLine();

foreach ((int lo, int hi) in new[] { (0, 2), (2, 5), (5, 7), (0, 7) })
{
    int sum = pre[hi + 1] - pre[lo];
    Console.WriteLine($"sum a[{lo}..{hi}] = pre[{hi + 1}] - pre[{lo}] = {pre[hi + 1]} - {pre[lo]} = {sum,2}   " +
                      $"[{string.Join(", ", a[lo..(hi + 1)])}]");
}

输出：

a   = [3, 1, 4, 1, 5, 9, 2, 6]
pre = [0, 3, 4, 8, 9, 14, 23, 25, 31]

sum a[0..2] = pre[3] - pre[0] = 8 - 0 =  8   [3, 1, 4]
sum a[2..5] = pre[6] - pre[2] = 23 - 4 = 19   [4, 1, 5, 9]
sum a[5..7] = pre[8] - pre[5] = 31 - 14 = 17   [9, 2, 6]
sum a[0..7] = pre[8] - pre[0] = 31 - 0 = 31   [3, 1, 4, 1, 5, 9, 2, 6]

关键是要记住：pre 按边界编号，而不是按元素编号。pre[2] 不是“索引 2 上的值”，而是“索引 2 之前的全部”。这样理解之后，区间公式就不用死记了：

sum a[lo..hi]  =  pre[hi + 1] - pre[lo]

pre[0] = 0 这个空前缀，让从索引 0 开始的区间不用特殊处理。如果只给 pre 分配 n 个格子而不是 n+1 个，你就得写那个特殊情况，还会写出隐蔽的错，白白丢掉二十分钟。

代价： 构建 O(n)，每次查询 O(1)，空间 O(n)。

适用场景： 数据不变，而区间查询很多。如果数据在查询之间会变，你需要的是树状数组（Fenwick 树）或线段树。前缀和一旦有修改，就得从修改的位置往后重建。

模式 12 — 前缀和加哈希表

统计和为目标值的子数组个数，允许出现负数。

先换个角度看。子数组 a[lo..hi] 的和等于 target，当且仅当 pre[hi+1] - pre[lo] == target，移项得到 pre[lo] == pre[hi+1] - target。所以一边遍历数组一边维护累计和，每一步都问：前缀 running - target 以前出现过吗？出现过几次？

prefix = 14 prefix = 21 之前出现过 当前 i 处 这一段的和是 21 − 14 = 7 每个索引处的累计和都是已知的。以这里结尾的一段，和等于目标值 当且仅当之前某个前缀等于 running − target。所以把每个前缀都存下来，再去查。

允许负数之后，取代滑动窗口的就是它。窗口要求“变大”就意味着“和更大”；前缀哈希表完全不需要这个条件。记得先放入 {0: 1}，也就是空前缀，否则所有从索引 0 开始的子数组都会漏掉。

// Negative values, so no sliding window can solve this: growing the window
// no longer means growing the sum.
int[] a = [3, 4, 7, -2, 2, 1, 4, 2];
int target = 7;

Dictionary<int, int> seen = new() { [0] = 1 };   // one empty prefix, sum 0
int running = 0, found = 0;

for (int i = 0; i < a.Length; i++)
{
    running += a[i];
    int need = running - target;
    int hits = seen.GetValueOrDefault(need);

    if (hits > 0)
        Console.WriteLine($"i={i}  running={running,2}  looking for {need,2}  found {hits}x  -> {hits} subarray(s) ending here");
    else
        Console.WriteLine($"i={i}  running={running,2}  looking for {need,2}  none");

    found += hits;
    seen[running] = seen.GetValueOrDefault(running) + 1;
}

Console.WriteLine($"\nsubarrays summing to {target}: {found}");

输出：

i=0  running= 3  looking for -4  none
i=1  running= 7  looking for  0  found 1x  -> 1 subarray(s) ending here
i=2  running=14  looking for  7  found 1x  -> 1 subarray(s) ending here
i=3  running=12  looking for  5  none
i=4  running=14  looking for  7  found 1x  -> 1 subarray(s) ending here
i=5  running=15  looking for  8  none
i=6  running=19  looking for 12  found 1x  -> 1 subarray(s) ending here
i=7  running=21  looking for 14  found 2x  -> 2 subarray(s) ending here

subarrays summing to 7: 6

这里靠两点撑着。

循环开始前，seen 里先放了 {0: 1}。这一项代表空前缀。没有它，所有从索引 0 开始的子数组都会漏掉，这个例子里 i=1 处的 [3, 4] 也在其中。这是这个模式里最常见的 bug，而且只有答案恰好从开头开始时才会暴露。

哈希表记的是出现次数，而不是有没有出现过，因为同一个前缀可能出现很多次，每一次都对应一个不同的子数组。看 i=7：前缀 14 之前出现过两次，所以有两个子数组在这里结束。

代价： 时间 O(n)，空间 O(n)。

适用场景： 数组里有负数，而你正想用滑动窗口。取代滑动窗口的就是这个模式。

模式 13 — 差分数组

现在倒过来用。你有一批区间更新要做，比如给索引 2 到 5 之间的每个元素加 3，这样的更新有很多，而你只需要最后的数组。

逐个元素地做更新，每次都是 O(区间长度)。换个做法，只记录每次更新从哪里开始、在哪里结束：

d[lo]      += v      // from here on, add v
d[hi + 1]  -= v      // from here on, stop adding it

不管区间多长，都只写两次。最后对 d 做一遍前缀和，就把这些标记还原成数值。

0 1 2 3 4 5 6 +2 [1..3] 0 2 0 0 -2 0 0 起点做标记，终点之后撤销 +3 [2..5] 0 2 3 0 -2 0 -3 还是写两次，与长度无关 −1 [0..2] -1 2 3 1 -2 0 -3 三次更新，只动了六个格子 累计和 -1 1 4 5 3 3 0 最后一遍扫描得出答案

差分数组就是倒过来的前缀和。每次区间更新不管区间多长，都只写两个格子，最后一遍扫描把标记还原成数值。第 7 个格子只是为了让 hi+1 始终不越界，最后会丢弃。

int n = 6;
int[] diff = new int[n + 1];       // one extra cell, so hi+1 is always in range

(int lo, int hi, int v)[] updates = [(1, 3, +2), (2, 5, +3), (0, 2, -1)];

foreach ((int lo, int hi, int v) in updates)
{
    diff[lo] += v;
    diff[hi + 1] -= v;
    Console.WriteLine($"add {v,2} to [{lo}..{hi}]   diff[{lo}] {v:+#;-#;0}, diff[{hi + 1}] {-v:+#;-#;0}   " +
                      $"-> [{string.Join(", ", diff)}]");
}

int[] final = new int[n];
int running = 0;
for (int i = 0; i < n; i++) { running += diff[i]; final[i] = running; }

Console.WriteLine($"\nrunning sum of diff -> [{string.Join(", ", final)}]");

// Brute force, to prove it.
int[] check = new int[n];
foreach ((int lo, int hi, int v) in updates)
    for (int i = lo; i <= hi; i++) check[i] += v;
Console.WriteLine($"element by element   -> [{string.Join(", ", check)}]");
Console.WriteLine($"same: {final.SequenceEqual(check)}");

输出：

add  2 to [1..3]   diff[1] +2, diff[4] -2   -> [0, 2, 0, 0, -2, 0, 0]
add  3 to [2..5]   diff[2] +3, diff[6] -3   -> [0, 2, 3, 0, -2, 0, -3]
add -1 to [0..2]   diff[0] -1, diff[3] +1   -> [-1, 2, 3, 1, -2, 0, -3]

running sum of diff -> [-1, 1, 4, 5, 3, 3]
element by element   -> [-1, 1, 4, 5, 3, 3]
same: True

最后加上暴力校验，是因为这个方法看起来不像能行。

d 分配了 n + 1 个格子，这样 hi 是最后一个索引时，d[hi + 1] 也不会越界。还原的时候从不读最后这个格子，它存在的唯一目的，是让“停止累加”那一次写入总有地方可写。

代价： 每次更新 O(1)，最后一次性 O(n)。

适用场景： 问题是先做 m 次区间更新，再读取结果。比如预订系统、航班座位统计、“每个点被多少个区间覆盖”。如果更新和查询交替进行，就需要树状数组。

模式 14 — 二维

同样的思路，多一个维度。pre[r][c] 存的是第 r 行严格上方、第 c 列严格左侧所有元素的和。

构建要用容斥原理，查询也一样。角上那块区域既属于上方的条带，也属于左侧的条带，两条都减掉，它就被减了两次。

A 已减去 B 已减去 C 已减去 所求 pre[r2+1][c2+1] — 到远端角为止的全部 − 上方的条带（C 和 A） − 左侧的条带（B 和 A） + A，因为 A 被减了两次 = 阴影块，只需读四次数组 漏掉最后的 + A，是这个模式里最常见的 bug。

角上那块区域既在上方的条带里，也在左侧的条带里，两条都减掉，它就被减了两次。把它加回来一次，不是事后打的补丁，容斥原理本来就是这样。

int[,] g = {
    {  1,  2,  3,  4 },
    {  5,  6,  7,  8 },
    {  9, 10, 11, 12 },
    { 13, 14, 15, 16 },
};
int rows = g.GetLength(0), cols = g.GetLength(1);

// pre[r, c] = sum of everything strictly above row r and left of column c.
int[,] pre = new int[rows + 1, cols + 1];
for (int r = 0; r < rows; r++)
    for (int c = 0; c < cols; c++)
        pre[r + 1, c + 1] = g[r, c] + pre[r, c + 1] + pre[r + 1, c] - pre[r, c];

Console.WriteLine("pre:");
for (int r = 0; r <= rows; r++)
{
    for (int c = 0; c <= cols; c++) Console.Write($"{pre[r, c],5}");
    Console.WriteLine();
}

int Query(int r1, int c1, int r2, int c2) =>
    pre[r2 + 1, c2 + 1] - pre[r1, c2 + 1] - pre[r2 + 1, c1] + pre[r1, c1];

Console.WriteLine();
foreach ((int r1, int c1, int r2, int c2) in new[] { (1, 1, 2, 2), (0, 0, 1, 1), (2, 0, 3, 3) })
{
    int brute = 0;
    for (int r = r1; r <= r2; r++) for (int c = c1; c <= c2; c++) brute += g[r, c];
    Console.WriteLine($"rows {r1}..{r2}, cols {c1}..{c2}  ->  {Query(r1, c1, r2, c2),3}   (brute force {brute,3})");
}

输出：

pre:
    0    0    0    0    0
    0    1    3    6   10
    0    6   14   24   36
    0   15   33   54   78
    0   28   60   96  136

rows 1..2, cols 1..2  ->   34   (brute force  34)
rows 0..1, cols 0..1  ->   14   (brute force  14)
rows 2..3, cols 0..3  ->  100   (brute force 100)

构建和查询用的是同一个 + - - + 形状，原因也相同。如果只能记住一件事，就记住最后一项是加号，加回的是被减了两次的那个角。

代价： 构建 O(rows × cols)，每次查询 O(1)。

适用场景： 查询的是网格里的矩形。图像问题、矩阵求和，以及任何“数一数这个框里有多少东西”的问题。

模式 15 — 前缀异或

异或和加法足够相似，上面这一套都能照搬，因为异或是它自己的逆运算：x ^ y ^ y == x。所以把前缀技巧里的 + 换成 ^ 照样成立，减法也变成再做一次 ^。

唯一值得放慢速度看的是移项这一步：

running ^ need == target      // what we want
need == running ^ target      // xor both sides by running
int[] a = [4, 2, 2, 6, 4];
int target = 6;

Dictionary<int, int> seen = new() { [0] = 1 };
int running = 0, found = 0;

for (int i = 0; i < a.Length; i++)
{
    running ^= a[i];
    int need = running ^ target;          // because x ^ need == target  =>  need == x ^ target
    int hits = seen.GetValueOrDefault(need);
    found += hits;

    Console.WriteLine($"i={i}  a[i]={a[i]}  prefixXor={running}  need={need}  matches={hits}");
    seen[running] = seen.GetValueOrDefault(running) + 1;
}

Console.WriteLine($"\nsubarrays with XOR {target}: {found}");

int brute = 0;
for (int i = 0; i < a.Length; i++)
{
    int x = 0;
    for (int j = i; j < a.Length; j++) { x ^= a[j]; if (x == target) brute++; }
}
Console.WriteLine($"brute force:            {brute}");

输出：

i=0  a[i]=4  prefixXor=4  need=2  matches=0
i=1  a[i]=2  prefixXor=6  need=0  matches=1
i=2  a[i]=2  prefixXor=4  need=2  matches=0
i=3  a[i]=6  prefixXor=2  need=4  matches=2
i=4  a[i]=4  prefixXor=6  need=0  matches=1

subarrays with XOR 6: 4
brute force:            4

结构上和模式 12 完全一样：同样预先放好的哈希表，同样的计数，只是把 + 换成了 ^。收录它正是为了这一点：一旦把前缀和看成“任何有逆运算的运算”，这个家族就远不止加法了。

代价： 时间 O(n)，空间 O(n)。

适用场景： 问题涉及区间异或。它还能推广到乘积（要小心 0），以及任何有逆运算的结合运算。

要点

  • pre 按边界编号，不按元素编号。 n+1 个格子，pre[0] = 0，sum a[lo..hi] = pre[hi+1] - pre[lo]，开头不需要特殊处理。
  • 滑动窗口用不了的时候，就用前缀和。 一旦出现负数，窗口变大就不再意味着和变大，窗口也就没有了依据。
  • 哈希表里先放 {0: 1}。 它就是空前缀。漏掉它，所有从索引 0 开始的答案都会消失，哪怕其他地方看起来都没问题。
  • 哈希表记次数，不是记有没有。 同一个前缀再次出现，就是又一次命中目标值。
  • 差分数组把一次区间更新变成两次写入。 d[lo] += v，d[hi+1] -= v，最后扫一遍。分配 n+1 个格子，第二次写入才总能落下。
  • 二维查询的最后一项是加号。 那个角被上方的条带和左侧的条带各减了一次，一共减了两次。
  • 它其实和加法无关。 任何有逆运算的运算都行，所以异或版本和原来的代码只差一个字符。

第 4 篇讲二分查找，重点是其中与“在有序数组里找某个元素”无关的那三分之二。

这篇文章对你有帮助吗？

点一颗爱心来评分！

平均评分 0 / 5. 投票总数： 0

还没有人投票。来做第一个评分的人吧。