当前位置：首页 > article >正文

（蓝桥杯）使用差分数组和前缀和解决区间更新问题——倒水

article 2025/1/17 3:10:39

题目描述

在一个桌子上摆放了 n 个杯子，每个杯子中有一定量的水。小 A 同学负责向杯子中倒水，他总共倒了 k 次，每次会向从第 L 个杯子到第 R 个杯子中添加 P 毫升的水（注意：水只可能增加，不可能减少）。

请问小 A 同学倒了 k 次水之后， n 个杯子每个杯子有多少毫升的水。

输入

第一行包含两个整数 n 和 k。

第二行包含 n 个整数，表示一开始每个杯子中水的毫升数。

接下来 k 行，每行包含三个整数 L,R,P，表示一次操作。

数据范围

1≤n,k≤100000。

1≤L≤R≤n,0≤P≤1000。

杯子中水的初始量在 [0,1000] 的范围内。

本题数据上保证所有的杯子在加水之后，水量值仍然在 int 范围内。

输出

共一行，包含 n 个整数，表示最终 n 个杯子每个杯子有多少毫升的水。

样式

输入：

8 3
1 2 10 8 1 5 1 1
7 8 12
1 8 4
2 3 12

输出

5 18 26 12 5 9 17 17

知识点

前缀和

前缀和是一种预处理技术，通过预先计算数组的前缀和，可以快速地求出任意区间的和。具体来说，对于一个数组 a，其前缀和数组 prefix 定义为：

prefix[i]=a[0]+a[1]+⋯+a[i]

通过前缀和数组，我们可以快速计算任意区间 [l, r] 的和：

sum(l,r)=prefix[r]−prefix[l−1]

例如，给定数组 a = [1, 2, 3, 4, 5]，其前缀和数组为 prefix = [1, 3, 6, 10, 15]。如果要计算区间 [1, 3] 的和，可以直接计算 prefix[3] - prefix[0] = 10 - 1 = 9。

差分

差分是一种用于处理区间更新问题的技术。差分数组 diff 定义为：

diff[i]=a[i]−a[i−1]

通过差分数组，我们可以高效地进行区间更新。例如，要将数组 a 的区间 [l, r] 中的每个元素增加 p，只需更新差分数组的两个位置：

diff[l]+=p

diff[r+1]−=p

前缀和与差分在处理数组问题时非常高效。前缀和可以将区间求和的时间复杂度从 O(n) 降低到 O(1)，而差分可以将区间更新的时间复杂度从 O(n) 降低到 O(1)。这两种技术在处理大规模数据时尤其有用，能够显著提高算法的效率。

例如，在处理多次区间更新和查询的问题时，可以先使用差分数组进行所有更新操作，然后通过一次前缀和计算还原出最终的数组，从而避免了每次更新都遍历整个数组的开销。

题解

我们将使用差分数组和前缀和来高效地解决这个问题。差分数组可以帮助我们快速进行区间更新，而前缀和可以将差分数组还原为最终的数组。

1. 读取输入

首先，我们需要从标准输入读取输入数据。
import sys

# 读取输入
n, k = map(int, sys.stdin.readline().split())
a = [int(i) for i in sys.stdin.readline().split()]
2. 构建差分数组

差分数组 b 的第 i 个元素表示 a[i] - a[i-1]。我们可以通过遍历数组 a 来构建这个数组。差分数组的第 0 个元素初始化为 a[0]。
b = [0] * (n + 10)
for i in range(n):
    if i == 0:
        b[i] = a[i]
    else:
        b[i] = a[i] - a[i - 1]
3. 进行区间更新

对于每次区间更新操作 l, r, p，我们只需要更新差分数组 b 的两个位置：b[l-1] 和 b[r]。
for i in range(k):
    l, r, p = map(int, sys.stdin.readline().split())
    b[l - 1] += p
    b[r] -= p
4. 计算前缀和

通过计算差分数组 b 的前缀和，我们可以还原出最终的数组 a。
for i in range(n):
    if i > 0:
        b[i] += b[i - 1]
    sys.stdout.write(str(b[i]))
    if i < n - 1:  # 在最后一个元素后不加空格
        sys.stdout.write(" ")
sys.stdout.write("\n")  # 最后换行
完整代码
import sys

# 读取输入
n, k = map(int, sys.stdin.readline().split())
a = [int(i) for i in sys.stdin.readline().split()]

# 构建差分数组
b = [0] * (n + 10)
for i in range(n):
    if i == 0:
        b[i] = a[i]
    else:
        b[i] = a[i] - a[i - 1]

# 进行区间更新
for i in range(k):
    l, r, p = map(int, sys.stdin.readline().split())
    b[l - 1] += p
    b[r] -= p

# 计算前缀和并输出结果
for i in range(n):
    if i > 0:
        b[i] += b[i - 1]
    sys.stdout.write(str(b[i]))
    if i < n - 1:  # 在最后一个元素后不加空格
        sys.stdout.write(" ")
sys.stdout.write("\n")  # 最后换行
总结

通过使用差分数组和前缀和，我们可以高效地进行区间更新操作。差分数组允许我们在 O(1) 时间内完成每次区间更新，而前缀和则可以在 O(n) 时间内还原出最终的数组。这种方法的时间复杂度为 O(n + k)，适用于大规模数据。