其实打比方来说就是:假如有一字符串ABCD,那么他的前缀就是A、AB、ABC、ABCD这四个从新从第一个字母一次往后开始拼接的字符串。当然这是字符串。但前缀和一般应用于数组,对于给定的数组a=[1,2,3,4],他的前 i 项和sum就表示数组中a[0]~a的和,具体为:二、定义
sum[0]=a[0]
sum[1]=a[0]+a[1]
......
sum=sum[0]+sum[1]+...+sum;
定义:前缀和是指某一序列的前 n 项和。基于前缀和的使用,我们一般把前缀和分为一维前缀和和二维前缀和。
基于一维数组的前缀和就是原数组前n个元素的和。
主要作用是可以在O(1)时间情况下快速的求出任一区间[l,r]内的元素之和。
欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) | Powered by Discuz! X3.4 |