算法之前缀和

生成前缀和数组

nums=[1,3,5,7,9]
pre=[0]

for n in nums:
    pre.append(pre[-1]+n)

也可以利用itertools.accumulate：

from itertools import accumulate
nums=[1,3,5,7,9]

pre=list(accumulate([0]+nums))

计算区间的和

$\sum_{k=i}^j nums[k]$，即nums[i]+nums[i+1]+……+nums[j-1]+nums[j]

根据定义

pre[j+1]=nums[0]+……+nums[i]+nums[i+1]+……+nums[j]

pre[i]=nums[0]+……+nums[i-1]

所以sum(nums[i:j+1])=pre[j+1]-pre[i]（O(1)的时间复杂度）

前缀异或

• 生成前缀数组

nums=[1,3,5,7,9]
pre=[0]

for n in nums:
    pre.append(pre[-1]^n)

from itertools import accumulate
import operator
nums=[1,3,5,7,9]

pre=list(accumulate([0]+nums,operator.xor))

• 使用

pre[j+1]^pre[i]

前缀积

• 生成前缀数组

nums=[1,3,5,7,9]
pre=[1]

for n in nums:
    pre.append(pre[-1]*n)

from itertools import accumulate
import operator
nums=[1,3,5,7,9]

pre=list(accumulate([1]+nums,operator.mul))

• 使用

pre[j+1]//pre[i]

二维前缀和

pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+nums[i][j]