前缀和以及差分数组

目录

1. 📝 前缀和数组
2. 概念
3. 作用
4. 代码示例
5. 📝 差分数组
6. 概念
7. 作用
8. 代码示例

📝 前缀和数组#

概念#

前缀和是指某序列的前i项和,即：prefix_sum[i] = num[1] + num[2]+···+num[i]

作用#

前缀和的最大用处是可以在O(1)时间内查询任意区间的和。例如,要查询数组num从第l到第r项的和，其和为: sum[l, r] = prefix_sum[r] - prefix_sum[l-1]

代码示例#

'''
构造前缀和
'''
def prefix_sum(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]
    return prefix

# 使用示例
arr = [1, 2, 3, 4, 5]
prefix = prefix_sum(arr)
print(prefix)  # 输出 [0, 1, 3, 6, 10, 15]

# 查询区间[2, 5]的和
l, r = 2, 5
sum = prefix[r] - prefix[l-1]
print(sum) # 输出14 (2 + 3 + 4 + 5)

📝 差分数组#

概念#

差分数组是指数组中每个元素与前一个元素的差(第一个元素除外), 即：diff[i] = num[i] - num[i-1] (i ≥ 1)

作用#

差分数组常用于高效处理区间修改操作。例如，要对数组num的第l到第r项每个元素加上一个值v，只需进行以下操作：cf[l]+= v; cf[r+1] -= v.

代码示例#

'''
构造差分数组
'''
def build_diff(arr):
    n = len(arr)
    diff = [0] * (n + 1)
    diff[1] = arr[0]
    for i in range(1, n):
        diff[i + 1] = arr[i] - arr[i - 1] 
    return diff

# 使用示例
arr = [1, 2, 3, 4, 5]
diff = build_diff(arr)
print(diff)  # 输出 [0, 1, 1, 1, 1, 1]

'''
区间修改
'''
def apply_diff(arr, updates):
    n = len(arr)
    diff = build_diff(arr)
    # 修改diff数组
    for l, r, v in updates:
        diff[l] += v
        if r + 1 <= n:
            diff[r + 1] -= v
    # 还原差分数组
    for i in range(1, n + 1):
        diff[i] += diff[i - 1]
    # 更新原数组
    for i in range(n):
        arr[i] = diff[i + 1]
    return arr

# 使用示例
arr = [1, 2, 3, 4, 5]
updates = [(1, 3, 2), (2, 4, 3)]
arr = apply_diff(arr, updates)
print(arr)  # 输出 [3, 7, 8, 9, 5]