前缀和&差分算法(Python版)

这篇具有很好参考价值的文章主要介绍了前缀和&差分算法(Python版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前缀和 & 差分

前缀和与差分是常用的区间优化方式,其中前缀和数组可以将区间查询的时间复杂度降为常数,而差分数组则可以将区间修改的时间复杂度降为常数。

一、前缀和

前缀和知识点简单易理解,但出题难度较大,需要根据题意挖掘出潜在的前缀和关系,建立辅助数组求解问题。

(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=yi1+xi(i>0)这个公式是生成前缀和数组的主要方式。

应用方式:

在创建前缀和数组以后,如果要查询原数组在区间[a,b]上的元素和,只需要使用公式 y b − y a − 1 y_b - y_{a-1} ybya1 即可在 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 1n200000,1ai200000

代码示例:文章来源地址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} ai1,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 ai1+ai,ai,ai+1+ai,注意到修改操作不会改变除这三个元素的序号以外的前缀和数组,而对前缀和数组来说,这个操作相当于互换了 b i − 1 b_{i-1} bi1 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(1n,m100),接下来 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={aiai1a1i[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。

输出格式:

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

代码示例:

# 二分法+三维差分
# 可以通过 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法基础】前缀和与差分

    😽 PREFACE 🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝 📢系列专栏: 算法 💪 种一棵树最好是十年前其次是现在 前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时

    2024年01月19日
    浏览(35)
  • 【算法基础2】前缀和与差分

    前缀和是某数列的前n项数的和,而差分则可以看做是前缀和的逆运算。前缀和与差分比起是一种算法,更像是一种解决问题的思路,通过构造一个特殊的数组,就可以让我们将某些复杂的问题简化。 (1)一维前缀和 已知一个数列a[n],用S[n]来表示这个数列的前n项和数列。

    2024年04月14日
    浏览(43)
  • C++基础算法前缀和和差分篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了前缀和和差分算法 Ⅵ .Ⅰ前缀和 ① 一维前缀和 : ​ 就是构建一个新的数组 s ,用来存储另一个数组的和前 i 个数组元素的和。用公式表达就是: S [ i ] = a [ 0 ]

    2024年02月16日
    浏览(51)
  • 蓝桥杯一维差分 | 算法基础

    ⭐ 简单说两句 ⭐ ✨ 正在努力的小新~ 💖 超级爱分享,分享各种有趣干货! 👩‍💻 提供:模拟面试 | 简历诊断 | 独家简历模板 🌈 感谢关注,关注了你就是我的超级粉丝啦! 🔒 以下内容仅对你可见~ 作者: 后端小知识 , CSDN后端领域新星创作者 |阿里云专家博主 CSDN 个

    2024年02月03日
    浏览(43)
  • 一文带你深入了解算法笔记中的前缀与差分(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月12日
    浏览(74)
  • 二维前缀和&二维差分(超详细,python版,其他语言也很轻松能看懂)

    上一篇文章讲解了一维前缀和一维差分,本篇进阶为二维。 二维前缀和跟一维前缀和求法相同,这里直接上例子。 数组a = [[1,2,2,1],[3,2,2,1],[1,1,1,1]] a数组如图: 则数组a的前缀和为:数组b[[1,3,5,6],[4,8,12,14],[5,10,15,18]] b数组如图: 前缀和递推公式为 b[i][j] = b[i - 1][j] + b[i][j - 1]

    2024年04月22日
    浏览(40)
  • [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新)

    [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板( 持续更新..... ) 目录 一、算法基础 1.Huffuman树 2.Sine之舞 3.数列排序 4.数列排序 5.特殊回文数 6.回文数 7.特殊的数字 8.杨辉三角形 9.高精度加法 10.Fibonacci数列 11.报时助手 12.回形取数 13.矩阵乘法 二、算法提高 1.印章

    2023年04月08日
    浏览(49)
  • 【算法】—前缀和与差分详解

     前缀和指一个数组的某下标之前的所有数组元素的和( 即数列的前n项求和 ),前缀和是一种重要的 预处理 ,能够降低算法的时间复杂度,可以快速地求出某一段的和,对于处理区间之间的问题是往往十分高效 相比较其他算法而言, 前缀和更像是一种解题的技巧,一种优

    2024年02月04日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包