算法学习笔记

First Post:

Last Update:

前缀和

前缀和是：

1
sum[i]=a[0]+a[1]+……+a[i]

前缀和的性质

1
2
3
4
#第一条性质用于处理前缀和
sum[i]=sum[i-1]+a[i]
#第二条性质可以在O（1）的时间内求出区间和
a[l]+……+a[r]=sum[r]-sum[l-1]

前缀和的目的就是快速求出区间之和

1
2
3
4
5
def get_sum(sum,l,r):
    if l==0:
        return sum[r]
    else:
        return sum[r]-sum[l-1]
≡