首页 > 其他 > 详细

4.前缀和

时间:2021-01-31 10:38:37      阅读:28      评论:0      收藏:0      [点我收藏+]

前缀和:

前缀和就是将前面所有的数相加和他本身想加得到的数

当你要算许多数组的时候可以用前缀和 例如:

1 10
20 50
12 38
45 67
27 89
因为用前缀和可以帮你减小时间复杂度
首先将每一个数的前缀和都算出来
再用数组中后一个数的前缀和减前一个数的前缀和
import random
a = [0]
b = 0
c = []
for i in range(100):
    a.append(random.randint(1,100))
"""
1 10
20 50
12 38
45 67
27 89
""" 
for j in range(5):
    t = input().split()
    t = map(int,t)
    t = list(t)
    c.append(t)
for k in range(1,len(a)):
    a[k] = a[k] + a[k - 1]
#print(a)
for m in range(5):
    print(a[c[m][1]] - a[c[m][0] - 1])  

4.前缀和

原文:https://www.cnblogs.com/Aaron-2008/p/14351549.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!