蓝桥杯第十五届抱佛脚(七)前缀和与差分 前缀和 前缀和算法是一种在数组处理中非常有效的技术,特别是当需要频繁查询某个固定区间内的元素和时。这种算法可以在 O(N) 的时间内预处理数组,并且能在 O(1) 的时间内回答区间和的查询。以下是前缀和算法的详细介绍: 基本概念 前缀和是一种对数组的预处理方法。假设有一个数组 arr[0], arr[1], ..., arr[n-1],前缀和数组 prefixSum 定义为: prefixSum[0] = arr[0] prefixSum[1] = arr