前缀和

前缀数组把一条长依赖链的所有中间累计值预先保存。查询前缀时直接读取；查询内部区间时，用逆元撤销左侧已经累计的部分。结合律允许改变括号，却不允许交换元素次序；逆元负责消去，交换律只在常见加法实例中额外成立。

这种预处理适合静态数据。修改 $a_j$ 会影响所有 $P_i$（$i\ge j$），直接维护需要线性时间；动态版本必须换成树状或分层摘要。

数组 $[2,1,4,3]$ 的加法前缀为 $[0,2,3,7,10]$，区间 $[2,4]$ 的和是 $10-2=8$。异或构成阿贝尔群，也可用同一边界消去；字符串拼接的自由幺半群没有全局逆元，但已知一个字符串确为另一个的前缀时，可唯一删去该前缀，得到剩余子串。这是有条件的左消去，并非群中的任意相除；返回共享切片与复制实际字符也有不同成本。一般幺半群则连这种消去都未必存在，例如最小值聚合会丢失此前较大的元素。

浮点加法在机器算术下不满足精确结合律。顺序前缀、树形 scan 和不同并行归约可能产生不同舍入结果；复杂度公式不因此失效，但数学等价与数值可复现性应分别说明，误差分析见浮点求和理路浮点求和：顺序、成对与补偿Floating-point summation · Compensated summation比较顺序、成对和补偿求和的误差传播，并区分准确性、可复现性与并行代价。。

二维前缀和利用包含—排除由四个角值求矩形和；这需要交换加法群。对非交换操作，没有不声明顺序约定的直接二维推广。

并行前缀扫描理路并行前缀扫描parallel prefix scan · parallel scan · prefix computation用上扫归约和下扫传播在线性工作、对数深度内计算任意幺半群运算的全部前缀。在任意幺半群上以 $\mathrm{\Theta }(n)$ 工作、$O(\log n)$ 深度计算全部前缀。Fenwick 树理路Fenwick 树Fenwick tree · Binary indexed tree用二进制最低位分解维护动态前缀聚合，支持单点更新与前缀查询的对数时间数据结构。则在标准阿贝尔群更新模型下支持动态点增量和前缀查询。两者实现的是不同更新/并行接口，不能只因都输出前缀就互换复杂度。

在有限序列的阿贝尔群范围内，差分数组理路差分数组Difference array用相邻值之差表示序列，使区间加法转化为两个端点更新。与前缀和互为变换：差分取相邻值之差，前缀累积恢复原序列。这份互逆对应限定在上述阿贝尔群范围内；一般幺半群前缀没有逆元，因而没有对应的无条件差分变换。

前缀计数、积分图、离线频率和扫描线事件都沿用相同边界思想。更高维、动态或输出敏感查询需要额外索引结构，不能从一维静态 $O(1)$ 区间和直接外推。