【蓝桥杯 | 备赛秘籍】真题解析之差分数组—一维、二维差分一套拿下，附蓝桥杯真题和代码实战！(上）
原创【蓝桥杯 | 备赛秘籍】真题解析之差分数组—一维、二维差分一套拿下，附蓝桥杯真题和代码实战！(上）
原创
计算机魔术师
发布于 2025-02-06 21:46:16
发布于 2025-02-06 21:46:16
代码可运行
运行总次数：0
代码可运行
🤵♂️ 个人主页: @AI_magician
📡主页地址： 作者简介：CSDN内容合伙人，全栈领域优质创作者。
👨💻景愿：旨在于能和更多的热爱计算机的伙伴一起成长！！🐱🏍
该文章收录专栏
[✨--- 《数据结构与算法章》 ---✨] [✨--- 《蓝桥杯备赛系列》 ---✨]
@toc
差分和前缀和其实是互逆的，为什么呢🙌，我们看到最后就会明白
差分数组
差分和前缀和其实是互逆的，一维差分我们可以知道， ai 是 b1...bi 的前缀和，如果我们要对区间 l , r 中的数都加上一个数c的话只需要让 bl += c 并且 br + 1 -= c 即可，这样用差分数组构建新数组时，区间 l , r 中的数都会在原基础上加上c。
一维差分
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。（核心思想便是提前计算好差分数组，通过差分数组与原数组之前的等式关系，从而只需要一次操作便可以对某个区间的元素进行增减）
算法技巧「==差分数组==」，类似前缀和技巧构造的 preSum 数组，对 nums 数组构造一个 diff 差分数组
对区间 nums[i..j] 的元素全部加 3，让 diff[i] += 3，再让 diff[j+1] -= 3 即可，只要花费 O(1) 的时间修改 diff 数组，就相当于给 nums 的整个区间做了修改。
注意：
1、差分数组的第一个元素和原数组一样，本质上是差分数组的数学公式逆推得到的结果。
把差分数组抽象成一个工具类便于调用，包含__init_构造方法和 increment 方法和 result 方法，代码如下：
//java codes
// 差分数组工具类
class Difference {
// 差分数组
private int[] diff;
/* 输入一个初始数组，区间操作将在这个数组上进行 */
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i, j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
// 用前缀和构造结果数组
num = res[0];
for (int i = 1; i < diff.length; i++) {
num += diff[i]
res[i] = num
}
return res;
}
}# python codes
# 差分数组工具类
class Difference:
# 差分数组
def __init__(self, nums: List[int]):
assert len(nums) > 0 # 用断言捕获异常 比print好
self.diff = [0] * len(nums) # O(n) 复杂度
# 根据初始数组构造差分数组
self.diff[0] = nums[0]
for i in range(1, len(nums)):
self.diff[i] = nums[i] - nums[i - 1]
# 给闭区间 [i, j] 增加 val（可以是负数）
def increment(self, i: int, j: int, val: int) -> None:
self.diff[i] += val
if j + 1 < len(self.diff):
self.diff[j + 1] -= val
# 返回结果数组
def result(self) -> List[int]:
res = [0] * len(self.diff)
# 根据差分数组构造结果数组
res[0] = self.diff[0]
for i in range(1, len(self.diff)):
res[i] = res[i - 1] + self.diff[i]
return res// c++ codes
// 差分数组工具类
class Difference {
// 差分数组
private:
int* diff;
/* 输入一个初始数组，区间操作将在这个数组上进行 */
public:
Difference(int* nums, int length) {
assert(length > 0);
diff = new int[length]();
diff[0] = nums[0];
for (int i = 1; i < length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i, j] 增加 val（可以是负数）*/
void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < sizeof(diff) / sizeof(diff[0])) {
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
int* result() {
int* res = new int[sizeof(diff) / sizeof(diff[0])]();
res[0] = diff[0];
for (int i = 1; i < sizeof(diff) / sizeof(diff[0]); i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
};区间加法 · 直接运用求解
假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 *k*** 个更新的操作。
其中，每个操作会被表示为一个三元组：startIndex, endIndex, inc，你需要将子数组 AstartIndex ... endIndex（包括 startIndex 和 endIndex）增加 inc。
请你返回 *k* 次操作后的数组。
拼车 根据应用问题转化
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
a = [0] * (max([i[2] for i in trips]) + 1) # 从0下标,确定拆分数组长度
# a = [0] * 1001
# 或车站编号从 0 开始，最多到 1000，也就是最多有 1001 个车站，那么我们的差分数组长度可以直接设置为 1001，这样索引刚好能够涵盖所有车站的编号 (运用条件！！)
# 构建差分数组
diff = Differnece(a)
for trip in trips: # 注意下车to的人数不算，故 trip[2] - 1
diff.increment(trip[1], trip[2] - 1, trip[0])
res = diff.result()
# print(res) 输出一定要注释掉，满了超多！！
for i in range(len(a)):
if res[i] > capacity:
return False
return True但是实际问题中，手敲代码只需要了解工具差分类的原理即可，不用写出工具类，直接面对过程过程，速度和编程效果更快。注意到这里的数组初始全0，那么拆分数组初始也是全0，不需要额外构造
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
diff = [0] * (max([i[2] for i in trips]) + 1) # 从0下标,确定拆分数组长度
for trip in trips: # 注意下车to的人数不算，故 trip[2] - 1
diff[trip[1]]+= trip[0]
if trip[2] - 1 + 1<len(diff):
diff[trip[2]] -= trip[0]
for i in range(1,len(diff)):
diff[i] = diff[i] + diff[i-1]
for i in range(len(diff)):
if diff[i] > capacity:
return False
return True蓝桥杯 重新排序（ 差分 + 前缀和计算得到原数组）
整体思路如下：
- 差分数组：利用差分数组统计每个区间的出现次数。(新思路！！不一定用于区间加减！)
- 前缀和方式求每个元素频次（区间元素频次概念很重要）
- 排序优化：将数组
arr和每个元素频次count都进行排序，使得频繁出现的元素在数组中获得较大的值。（频次最高的乘于最大值之和）
class sollution:
def sovle():
"""
以下方法不可行！！审题！！！！！有m个区间！！！判断不了交集！！以下代码只适合2个区间！！！审题！ 审题时间不能省！！！
"""
# 输入
length = int(input().strip())
lists = list(map(int, input().strip().split(" ")))
n = int(input().strip())
pre1,ord1 = list(map(int, input().strip().split(" ")))
pre2,ord2 = list(map(int, input().strip().split(" ")))
# 输入后检查
# print(length,lists,n,pre1,ord1,pre2,ord2)
# 处理数据
pre_sum1 = sum(lists[pre1-1:ord1])
pre_sum2 = sum(lists[pre2-1:ord2])
pre_sum = pre_sum1 + pre_sum2
# 算法
## 数组区间 判断是否有交集,四种区间分布（待优化)
if pre1 >= pre2 and ord1 <= ord2:
k = ord1 - pre1 + 1
temp_list = [0] * (ord2 - pre2 + 1)
j = 0
for i in range(pre2-1,ord2): # python 一个循环只能有一个i 可以又多一个j吗？
temp_list[j] = (lists[i],i) # 值与下标的元组序列
j += 1
temp_list.sort(key=lambda x:x[0],reverse=True)
for i in range(0,k):
lists[pre1 - i],lists[temp_list[i][1]] = lists[temp_list[i][1]], lists[pre1 - i]
ord_sum1 = sum(lists[pre1-1:ord1])
ord_sum2 = sum(lists[pre2-1:ord2])
ord_sum = ord_sum1 + ord_sum2
print(ord_sum - pre_sum)
elif pre1 <= pre2 and ord1 >= ord2:
k = ord2 - pre2 + 1
temp_list = [0] * (ord1 - pre1 + 1)
j = 0
for i in range(pre1-1,ord1): # python 一个循环只能有一个i 可以又多一个j吗？
temp_list[j] = (lists[i],i) # 值与下标的元组序列
j += 1
temp_list.sort(key=lambda x:x[0],reverse=True)
for i in range(0,k):
lists[pre2 - i],lists[temp_list[i][1]] = lists[temp_list[i][1]], lists[pre2 - i]
ord_sum1 = sum(lists[pre1-1:ord1])
ord_sum2 = sum(lists[pre2-1:ord2])
ord_sum = ord_sum1 + ord_sum2
print(ord_sum - pre_sum)
elif pre1 < pre2 and ord1 > pre2 and ord1 < ord2:
k = ord1 - pre2 + 1
temp_list = [0] * (ord2 - pre1 + 1)
j = 0
# 排序数组并记录对应下标
for i in range(pre1-1,ord2): # python 一个循环只能有一个i 可以又多一个j吗？
temp_list[j] = (lists[i],i) # 值与下标的元组序列
j += 1
temp_list.sort(key=lambda x:x[0],reverse=True) # 注意默认是从小到大！
# 交换交集内的元素为最大元素
for i in range(0,k):
lists[pre2 - i],lists[temp_list[i][1]] = lists[temp_list[i][1]], lists[pre2 - i]
# 计算修改后的sum
ord_sum1 = sum(lists[pre1-1:ord1])
ord_sum2 = sum(lists[pre2-1:ord2])
ord_sum = ord_sum1 + ord_sum2
# print(temp_list,lists,ord_sum,pre_sum)
print(ord_sum - pre_sum)
elif pre1 > pre2 and ord1 < pre2 and ord1 > ord2:
k = ord2 - pre1 + 1
temp_list = [0] * (ord1 - pre2 + 1)
j = 0
for i in range(pre2-1,ord1): # python 一个循环只能有一个i 可以又多一个j吗？
temp_list[j] = (lists[i],i) # 值与下标的元组序列
j += 1
temp_list.sort(key=lambda x:x[0],reverse=True)
for i in range(0,k):
lists[pre1 - i],lists[temp_list[i][1]] = lists[temp_list[i][1]], lists[pre1 - i]
ord_sum1 = sum(lists[pre1-1:ord1])
ord_sum2 = sum(lists[pre2-1:ord2])
ord_sum = ord_sum1 + ord_sum2
print(ord_sum - pre_sum)
else:
print(0)
sollution.sovle()def solve():
# 读取输入
n = int(input()) # 数组的大小
arr = list(map(int, input().split())) # 数组 A
m = int(input()) # 查询的数量
# 差分数组初始化
diff = [0] * (n + 2) # 使用n+1＋1（从1开始数）大小的差分数组
# 处理每个查询并更新差分数组
for _ in range(m):
l, r = map(int, input().split())
diff[l] += 1
diff[r + 1] -= 1
# 统计每个位置的出现次数 ，前缀和方式相加，恰好是对应每个元素的总出现次数
cnt = [0] * (n + 1)
num = 0
for i in range(1, n + 1):
num += diff[i] # 计算前缀和得到每个位置的出现次数
cnt[i] = num
# 计算原数组的总和(不用算区间，直接计算元素频次和元素值！！)
sum1 = 0
for i in range(1, n + 1):
sum1 += arr[i - 1] * cnt[i] # 计算原数组的查询和
# 对 arr 和 cnt 数组进行排序
# print(arr,cnt)
arr.sort(reverse=True) # 排序原数组
cnt.sort(reverse=True) # 出现次数数组从大到小排序
# print(arr,cnt)
# 计算最优数组的总和
sum2 = 0
for i in range(n): # 从0开始排序 从0-n
sum2 += arr[i] * cnt[i] # 计算最优数组的查询和
# print(sum1,sum2)
# 输出答案
print(sum2 - sum1)
# 调用解题函数
solve()
🤞到这里，如果还有什么疑问🤞
🎩欢迎私信博主问题哦，博主会尽自己能力为你解答疑惑的！🎩
🥳如果对你有帮助，你的赞是对博主最大的支持！！🥳原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
