前缀和

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

这种预处理适合静态数据。修改 $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用相邻值之差表示序列，使区间加法转化为两个端点更新。与前缀和互为变换：差分取相邻值之差，前缀累积恢复原序列。equivalent_to 只在这一共同范围内成立；一般幺半群前缀没有逆元，因而没有对应的无条件差分变换。

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