写在前面
在数据结构和算法中，前缀和（Prefix Sum）是一种常见的技术，用于快速计算数组或序列中某个位置之前的元素的和。除了常规的前缀和之外，还有一些常见的前缀和的变种
前缀和的种类
常规前缀和
- 对于数组
nums，前缀和prefixSum[i]表示从索引 0 到索引 i（包括 i）的元素的和。 prefixSum[i] = nums[0] + nums[1] + ... + nums[i]
差分前缀和（Difference Prefix Sum）
- 差分前缀和是常规前缀和的一种变种，它表示相邻元素之间的差值的前缀和。
- 差分前缀和可以用于高效地修改原始数组中的连续子数组的值。
diffPrefixSum[i] = nums[i] - nums[i-1]
二维前缀和
- 适用于二维数组，表示从左上角（或右上角、左下角、右下角）到某个位置的矩形区域的和。
prefixSum[i][j] = sum of nums[k][l] for 0 ≤ k ≤ i, 0 ≤ l ≤ j
区间前缀和
- 用于计算数组中任意两个位置之间的元素的和。通过差分前缀和，可以高效地计算区间和。
rangeSum(i, j) = prefixSum[j] - prefixSum[i-1]
树状数组（Binary Indexed Tree）
- 也称为 Fenwick 树，用于高效地计算数组中前缀和和区间和。它是一种特殊的数据结构
- 可以在 O(log n) 的时间复杂度内更新和查询前缀和。
前缀最大值（Prefix Maximum）
- 用于计算数组中某个位置之前的最大值。
- 通过维护一个当前的最大值，在计算前缀和的同时记录最大值，可以在 O(1) 的时间复杂度内获取到前缀的最大值。
前缀最小值（Prefix Minimum）
- 类似于前缀最大值，用于计算数组中某个位置之前的最小值。
前缀乘积（Prefix Product）
- 用于计算数组中某个位置之前的元素的乘积。
- 通过维护一个当前的乘积，在计算前缀和的同时记录乘积，可以在 O(1) 的时间复杂度内获取到前缀的乘积。
异或前缀和（XOR Prefix Sum）
- 异或前缀和是指将数组中前缀的元素进行异或操作得到的前缀和。
xorPrefixSum[i] = nums[0] ^ nums[1] ^ ... ^ nums[i]- 异或前缀和常用于解决一些问题
- 例如找出数组中出现奇数次的元素
- 判断一个数组中是否存在两个元素的异或结果为指定值等。