一维静态前缀和

一维静态前缀和是一种预处理技术，用于快速计算数组中任意区间的元素和。
通过预先计算从数组起始位置到每个位置的累加和，可以将区间求和的时间复杂度从 $\mathcal{O}(n)$ 优化到 $\mathcal{O}(1)$ 。

基本概念

前缀和的核心思想是：

预处理数组，计算前缀和数组
前缀和数组的第 $i$ 个元素表示原数组前 $i$ 个元素的和
任意区间 $[l,r]$ 的和可以通过 $prefix[r] - prefix[l-1]$ 得到
适用于频繁查询区间和的场景

实现方式

前缀和的实现步骤：

创建前缀和数组（通常比原数组多一个位置）
预处理计算前缀和
使用前缀和数组进行区间查询

基本实现

c++
java
python

class PrefixSum {
private:
    vector<int> prefix;

public:
    PrefixSum(vector<int>& nums) {
        int n = nums.size();
        prefix.resize(n + 1);
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    // 查询区间[left, right]的和
    int rangeSum(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
};

class PrefixSum {
    private int[] prefix;
    
    public PrefixSum(int[] nums) {
        int n = nums.length;
        prefix = new int[n + 1];
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }
    
    // 查询区间[left, right]的和
    public int rangeSum(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

class PrefixSum:
    def __init__(self, nums):
        n = len(nums)
        self.prefix = [0] * (n + 1)
        # 计算前缀和
        for i in range(n):
            self.prefix[i + 1] = self.prefix[i] + nums[i]
    
    # 查询区间[left, right]的和
    def range_sum(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

应用场景

前缀和在很多问题中都有应用：

区间和查询
统计子数组特征
优化动态规划
处理差分数组
二维前缀和的基础

示例：和为k的子数组个数

cpp
java
python

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    count[0] = 1;
    int sum = 0, result = 0;
    
    for (int num : nums) {
        sum += num;
        if (count.find(sum - k) != count.end()) {
            result += count[sum - k];
        }
        count[sum]++;
    }
    
    return result;
}

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int sum = 0, result = 0;
    
    for (int num : nums) {
        sum += num;
        if (count.containsKey(sum - k)) {
            result += count.get(sum - k);
        }
        count.put(sum, count.getOrDefault(sum, 0) + 1);
    }
    
    return result;
}

def subarray_sum(nums, k):
    count = {0: 1}
    sum = result = 0
    
    for num in nums:
        sum += num
        if sum - k in count:
            result += count[sum - k]
        count[sum] = count.get(sum, 0) + 1
    
    return result