前缀和

概述

前缀和（Prefix Sum）是数组的一种预处理技术，构造前缀和数组 $S[i]=A[0]+A[1]+\cdots +A[i-1]$，使得任意区间 $[l,r)$ 的求和可在 $O(1)$ 时间内完成。前缀和的构造时间为 $O(n)$。在并行计算中，并行前缀和（扫描算法）可在 $O(\log n)$ 时间内使用 $O(n)$ 的 work 完成。

定义

前缀和（Prefix Sum）

给定数组 $A[\mathrm{0..}n-1]$，其前缀和数组 $S[\mathrm{0..}n]$ 定义为：

$S[0]=0,S[i]={\sum }_{j=0}^{i-1}A[j](1\le i\le n)$

利用前缀和数组，任意区间和可在 $O(1)$ 时间内计算：

${\sum }_{j=l}^{r-1}A[j]=S[r]-S[l]$

并行前缀和（Parallel Prefix Sum / Scan）

并行前缀和（扫描算法）使用动态多线程模型，在 $O(\log n)$ 的 span 和 $O(n)$ 的 work 内完成前缀和计算。算法采用上-下扫描（up-sweep / down-sweep）两阶段：

1. 上扫描：自底向上构建部分和的树结构
2. 下扫描：自顶向下将部分和分配到正确位置

核心性质

性质	描述	备注
构造时间	$O(n)$（串行）	一次遍历即可
区间查询	$O(1)$	$S[r]-S[l]$
空间开销	$O(n)$	需要额外的前缀和数组
并行 span	$O(\log n)$	适合并行化
并行 work	$O(n)$	work-optimal
并行度	$O(n/\log n)$	足够利用多核处理器

应用场景

• 区间求和查询：给定数组，快速回答任意区间的元素之和
• 差分数组：前缀和的逆运算，用于区间批量更新
• 并行算法基础：许多并行算法（如并行归并排序、并行筛选）的基础组件
• 图像处理：积分图（integral image）用于快速计算矩形区域特征
• 字符串哈希：利用前缀和计算子串的哈希值，实现 $O(1)$ 子串比较
• 计数排序/基数排序：前缀和用于确定每个元素在排序结果中的位置

串行 vs 并行前缀和

比较维度	串行前缀和	并行前缀和
Work	$\Theta (n)$	$\Theta (n)$
Span	$\Theta (n)$	$\Theta (\log n)$
并行度	1	$\Theta (n/\log n)$
适用场景	单处理器	多核/并行系统

参见

• 动态多线程 — 并行前缀和的计算模型
• 分治法 — 并行前缀和的上扫描阶段使用分治思想