前缀和 & 差分
前缀和与差分是常用的区间优化方式,其中前缀和数组可以将区间查询的时间复杂度降为常数,而差分数组则可以将区间修改的时间复杂度降为常数。
一、前缀和
前缀和知识点简单易理解,但出题难度较大,需要根据题意挖掘出潜在的前缀和关系,建立辅助数组求解问题。
(1)一维前缀和
定义:
对数组 x 0 , x 1 , x 2 , . . . , x n x_0,x_1,x_2,...,x_n x0,x1,x2,...,xn,对其进行区间查询的时间复杂度是 O ( n ) O(n) O(n) 为了提高区间查询的效率,可以引入前缀和数组 y 0 , y 1 , . . . y n y_0,y_1,...y_n y0,y1,...yn,前缀和数组有以下定义:
y 0 = x 0 y 1 = x 0 + x 1 y 2 = x 0 + x 1 + x 2 . . . y_0 = x_0\\ y_1 = x_0 + x_1\\ y_2 = x_0 + x_1 + x_2... y0=x0y1=x0+x1y2=x0+x1+x2...
创建方式:
由定义可知,前缀和数组有递推生成公式: y i = y i − 1 + x i ( i > 0 ) y_i = y_{i-1} + x_i(i > 0) yi=yi−1+xi(i>0)这个公式是生成前缀和数组的主要方式。
应用方式:
在创建前缀和数组以后,如果要查询原数组在区间[a,b]上的元素和,只需要使用公式 y b − y a − 1 y_b - y_{a-1} yb−ya−1 即可在 O ( 1 ) O(1) O(1) 的时间复杂度上求出区间元素和。
例题 1:和与乘积(蓝桥杯第12届国赛真题)
题目描述:
给定一个数列 A = ( a 1 , a 2 , . . . , a n ) A = (a_1,a_2,...,a_n) A=(a1,a2,...,an),问有多少个区间 [ L , R ] [L,R] [L,R] 满足区间内所有元素的和等于区间内所有元素的乘积。
输入格式:
输入第一行包含一个整数n。第二行包含n个整数,依次表示数列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an
输出格式:
输出仅一行,包含一个整数表示满足如上条件的区间的个数。
提示:
1 ≤ n ≤ 200000 , 1 ≤ a i ≤ 200000 1 ≤ n ≤ 200000,1 ≤ a_i ≤ 200000 1≤n≤200000,1≤ai≤200000。
代码示例:文章来源地址https://www.toymoban.com/news/detail-853902.html
# 自己写的粗糙前缀和代码,超时了
n = int(input())
a = [int(i) for i in input().split()]
# 创建前缀和数组
b = [0]*n
b[0] = a[0]
for i in range(1, n):
b[i] = b[i-1] + a[i]
# 利用滑动窗口求出区间乘积
ans = 0
# 区间长度
for l in range(1,n+1):
temp = 1
for right in range(n):
if right < l-1:
temp *= a[right]
elif right == l-1:
# begin to judge
temp *= a[right]
if temp == b[right]:
ans += 1
else:
temp *= a[right]
temp //= a[right-l]
if temp == b[right] - b[right-l]:
ans += 1
print(ans)
# 观察规律,进行剪枝
# 注意到数组中1的特殊作用,正是有了1才让元素之和的增长速度有可能追上元素之积
# 类比前缀和的思想,使用多个数组存储原数组的各种信息
# input
n = int(input())
a = [int(i) for i in input().split()]
# initialize
# 创建数组num[],存储原数组中所有的非1元素,注意非1元素之间的相对顺序不变
num = []
# 创建数组one_cnt[],one_cnt[i]存储num[i]在原数组中前面连续的1的个数
one_cnt = []
# 填充这几个辅助数组
cnt = 0 # 记录当前非1元素前缀1的个数
for i in range(n):
if a[i] == 1:
cnt += 1
else:
# 每遇到一个非1元素,就存储该元素前连续1的个数,然后清零重新计数
one_cnt.append(cnt)
cnt = 0
num.append(a[i])
if one_cnt:
# 注意还要将最后一个非1元素右边的连续1的个数也记录下来
one_cnt.append(cnt)
# 填充add数组
# 创建前缀和数组add[],add[i]是num[i]在原数组中的前缀和(包含它以及它以前所有元素的和)
add = [0]*len(num)
for i in range(len(num)):
if i == 0:
add[0] = one_cnt[0] + num[0]
else:
add[i] = add[i-1] + one_cnt[i] + num[i]
# 开始正式求解
ans = n # 每一个长度为1的区间都符合题意,一共有n个
# 整个原数组的元素和
all_sum = add[-1] + one_cnt[-1]
# 遍历非1数组num
for left in range(len(num)-1):
# create a variable to record the multiple result of all of the elements in the interval
m = num[left]
# 对left = 0特别处理
if left == 0:
for r in range(left+1,len(num)):
m *= num[r]
if m > all_sum:
break
diff = m - (add[r] - one_cnt[left])
if diff > 0:
if diff <= one_cnt[r+1] + one_cnt[left]:
# 这里的ll和rr记录了左右两侧最多能够取多少个1到当前的子序列中
# 相当于求一个长度为diff的滑块在长度为ll+rr的滑槽中滑动的位置数
# 受限于滑块本身的长度,部分坐标(共diff-1个)是取不到的,所以减去
ll = min(diff,one_cnt[left])
rr = min(diff,one_cnt[r+1])
ans += ll+rr-diff+1
elif diff == 0:
ans += 1
continue
for right in range(left+1,len(num)):
# because the 1 will not change the result of multiple,so ignore them
m *= num[right]
if m > all_sum:
# 乘积超过总和,直接排除
break
# 再看乘积与区间和的差值
d = m - (add[right] - add[left-1] - one_cnt[left])
if d > 0:
# 尝试用左右两侧的1补齐
if d <= one_cnt[right+1]+one_cnt[left]:
# 可以补全
# 但因为1有多种取法,所以有多种情况
# ans += min()+1 + min()+1 - (d+1)
l_case = min(d,one_cnt[left])
r_case = min(d,one_cnt[right+1])
ans += l_case+r_case-d+1
elif d == 0:
ans += 1
print(ans)
例题 2:字串简写(蓝桥杯第14届省赛真题)
题目描述:
程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18n,Kubernetes (注意连字符不是字符串的一部分)简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中,我们规定长度大于等于 K 的字符串都可以采用这种简写方法(长度小于 K 的字符串不配使用这种简写)。
给定一个字符串 S 和两个字符 c 1 c_1 c1 和 c 2 c_2 c2,请你计算 S S S 有多少个以 c 1 c_1 c1 开头 c 2 c_2 c2 结尾的字串可以使用这种简写。
输入格式:
第一行包含一个整数 K K K,第二行包含一个字符串 S S S 和两个字符 c 1 c_1 c1 和 c 2 c_2 c2。
输出格式:
输出一个整数表示答案。
代码示例:
# 可以直接暴力,但肯定会超时,这种题目评测数据很大,纯暴力拿不了几分
k = int(input())
s,c1,c2 = input().split()
# 创建两个辅助数组,存储字符串中c1和c2字符的下标
begin = []
end = []
for i in range(len(s)):
if s[i] == c1:
begin.append(i)
if s[i] == c2:
end.append(i)
# 两重for循环判断每一对c1和c2是否符合题意
ans = 0
b = len(begin)
e = len(end)
startIndex = 0
for i in range(b):
for j in range(startIndex, len(e)):
# 如果不满足题意,直接跳过
if end[j]-begin[i]+1 < k:
continue
# 满足题意,直接利用end[]数组的长度计算出后续还有多少个符合条件的c2
ans += e - j
# 更新startIndex,下一次从j开始搜索,因为 begin[i+1] > begin[i]
startIndex = j
# 直接结束本轮搜索
break
print(ans)
例题 3:灵能传输
解题思路:
对三个相邻的数 a i − 1 , a i , a i + 1 a_{i-1},a_i,a_{i+1} ai−1,ai,ai+1,无论 a i < 0 a_i < 0 ai<0 还是 a i > 0 a_i > 0 ai>0 都可以进行操作将其变为 a i − 1 + a i , − a i , a i + 1 + a i a_{i-1}+a_i,-a_i,a_{i+1}+a_i ai−1+ai,−ai,ai+1+ai,注意到修改操作不会改变除这三个元素的序号以外的前缀和数组,而对前缀和数组来说,这个操作相当于互换了 b i − 1 b_{i-1} bi−1 和 b i b_i bi 的值。
(2)二维前缀和
二维前缀和出题特征明显,往往会直接指出需要进行二维区间查询操作,但不需要进行二维区间修改。对二维前缀和的求解和应用基本上是围绕容斥定理进行的。
例题 1:P1387 最大正方形
题目描述:
在一个 n × m n\times m n×m 的只包含 0 0 0 和 1 1 1 的矩阵里找出一个不包含 0 0 0 的最大正方形,输出边长。
输入格式:
输入文件第一行为两个整数 n , m ( 1 ≤ n , m ≤ 100 ) n,m(1\leq n,m\leq 100) n,m(1≤n,m≤100),接下来 n n n 行,每行 m m m 个数字,用空格隔开, 0 0 0 或 1 1 1。
输出格式:
一个整数,最大正方形的边长。
def init(c):
return int(c)^1
def check(l):
if l == 0:
return True
global n,m,matrix, add
# 检查是否存在符合题意的边长为l的正方形区间
for i in range(n-l+1):
for j in range(m-l+1):
# 计算区间和是否为0
temp = add[i+l-1][j+l-1]
if i > 0 and j > 0:
temp = temp - add[i+l-1][j-1] - add[i-1][j+l-1] + add[i-1][j-1]
elif i > 0 and j == 0:
temp = temp - add[i-1][j+l-1]
elif i == 0 and j > 0:
temp = temp - add[i+l-1][j-1]
if temp == 0:
return True
return False
n,m = map(int,input().split())
matrix = []
for i in range(n):
matrix.append([init(j) for j in input().split()])
# 初始化二维前缀和数组
add = [[0]*m for i in range(n)]
for i in range(m):
add[0][i] = matrix[0][i]
for i in range(1,n):
add[i][0] = matrix[i][0]
for i in range(1,n):
for j in range(1,m):
add[i][j] = matrix[i][j] + add[i-1][j] + add[i][j-1] - add[i-1][j-1]
# 二分法搜索区间和为0的最大正方形区间
left = 0
right = min(n,m)
while left < right:
mid = (left+right+1)//2
if check(mid):
left = mid
else:
right = mid-1
print(right)
二、差分
差分是一种和前缀和类似的概念,二者都通过构建辅助数组存储原数组的信息,从而简化计算过程,提高效率。不同的是,差分数组用于记录原数组中相邻两个元素的差值。
差分数组的作用:
将区间修改的时间复杂度从线性级降低为常数级,但用差分数组实现的单点查询操作时间复杂度为线性,所以差分数组主要用于需要多次区间修改后读取数值的情景。
差分数组的创建方式:
b i = { a i − a i − 1 i ∈ [ 2 , n ] a 1 i = 1 b_i=\begin{cases}a_i-a_{i-1}\,&i \in[2,n] \\ a_1\,&i=1\end{cases} bi={ai−ai−1a1i∈[2,n]i=1
差分数组的读取方式:
差分数组的前缀和数组就是原数组,所以在差分数组中进行单点读取的时间复杂度是线性的。
例题 1:棋盘(蓝桥杯第14届省赛真题)
题目描述:
小蓝拥有一个 n×n 大小的棋盘,一开始棋盘上全都是白子。小蓝进行了 m 次操作,每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色,黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。
输入格式:
输入的第一行包含两个整数 n , m n,m n,m 用一个空格分隔,分别表示棋盘的大小和操作数。接下来 m 行每行包含四个整数 x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2 x1,y1,x2,y2 ,四个数用空格隔开,表示将 x 1 x_1 x1行 和 x 2 x_2 x2行与 y 1 y_1 y1列 和 y 2 y_2 y2列之间的所有棋子取反。
输出格式:
输出 n 行,每行 n 个 0 或 1 表示该位置棋子的颜色。如果是白色则输出 0,否则输出 1。
代码示例:
# 差分
# 偶数表示棋子是白色,奇数表示棋子是黑色
# 初始值为0
n,m = map(int,input().split())
# initialize the board
# b是一个棋盘的差分数组
b = [[0]*(n+2) for i in range(n+2)]
# begin to run the instructions
# 每一条指令都让区间内所有元素加一,最后看元素的奇偶性决定最终的棋子状态
for _ in range(m):
x1,y1,x2,y2 = map(int,input().split())
b[x1][y1] += 1
b[x2+1][y1] -= 1
b[x1][y2+1] -= 1
b[x2+1][y2+1] += 1
# 还原原数组,计算出结果
a = [[0]*(n+2) for i in range(n+2)]
for i in range(1,n+1):
for j in range(1,n+1):
a[i][j] = (a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j]+2)%2
print(a[i][j],end = '')
print()
例题 2:三体攻击
题目链接:三体攻击(蓝桥杯)
题目描述:
三体人将对地球发起攻击。为了抵御攻击,地球人派出了 A×B×C 艘战舰,在太空中排成一个 A 层 B 行 C 列的立方体。
其中,第 i 层第 j 行第 k 列的战舰(记为战舰 (i,j,k))的生命值为 d(i,j,k)。三体人将会对地球发起 m 轮“立方体攻击”,每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地,第 t 轮攻击用 7 个参数 lat,rat,lbt,rbt,lct,rct,ht描述;
所有满足 i∈[lat,rat],j∈[lbt,rbt],k∈[lct,rct] 的战舰 (i,j,k) 会受到 ht 的伤害。
如果一个战舰累计受到的总伤害超过其防御力,那么这个战舰会爆炸。
地球指挥官希望你能告诉他,第一艘爆炸的战舰是在哪一轮攻击后爆炸的。
输入描述:
第一行包括 4 个正整数 A,B,C,m;第二行包含 A×B×C 个整数,其中第 ((i−1)×B+(j−1))×C+(k−1)+1 个数为 d(i, j, k);
第 3 到第 m+2 行中,第 (t − 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, ht。
输出格式:
输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。文章来源:https://www.toymoban.com/news/detail-853902.html
代码示例:
# 二分法+三维差分
# 可以通过 75% 的测试样例,剩余 25% 超时
# 本题需要使用多次单点查询,由于战舰爆炸与否具有二分特性,所以可以使用二分法确定首个战舰爆炸的时刻
# 使用三维差分数组提高区间修改的效率
def check(times):
# 检查经过times轮的攻击后是否存在爆炸的战舰、
global a,b,c,hits
reduce = [[[0 for i in range(c+2)] for j in range(b+2)] for k in range(a+2)]
for t in range(times):
la,ra,lb,rb,lc,rc,v = hits[t]
reduce[la][lb][lc] += v
reduce[la][lb][rc+1] -= v
reduce[la][rb+1][lc] -= v
reduce[ra+1][lb][lc] -= v
reduce[ra+1][rb+1][lc] += v
reduce[ra+1][lb][rc+1] += v
reduce[la][rb+1][rc+1] += v
reduce[ra+1][rb+1][rc+1] -= v
# 根据差分数组还原出原数组,并和防御值进行比较
# 注意原坐标从1开始计数
for i in range(1,a+1):
for j in range(1,b+1):
for k in range(1,c+1):
# 将差分数组转换成其所对应的前缀和数组
# 容斥定理
reduce[i][j][k] += reduce[i-1][j][k]+reduce[i][j-1][k]+reduce[i][j][k-1]-reduce[i-1][j-1][k]-reduce[i-1][j][k-1]-reduce[i][j-1][k-1]+reduce[i-1][j-1][k-1]
# 检查是否爆炸
if reduce[i][j][k] > d[(k-1)+c*((j-1)+b*(i-1))]:
return True
return False
a,b,c,m = map(int,input().split())
d = [int(i) for i in input().split()]
hits = [list(map(int,input().split())) for i in range(m)]
# binary search
left = 1
right = m
while left < right:
mid = (left+right)//2
if check(mid):
right = mid
else:
left = mid+1
print(left)
到了这里,关于前缀和&差分算法(Python版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!