题目
分析
前缀和是一个重要的概念,需要牢牢掌握。本题是入门题,旨在帮助学生掌握这个基本概念和应用。
前缀和概念和应用
前缀和(prefix sum)用于快速计算数组任意区间的和。设数组为a
,构造前缀和数组s
:
s[i] = a[1] + a[2] + ...... + a[i] //(常用 1-based)。
则任意区间[l, r]
的和为:sum(l, r) = s[r] - s[l - 1]
。
显然,有了前缀和数组后,在求任意一个区间和的时候,只要进行一次加法操作,而代价只是多了一个存放前缀和数组的空间——典型的以空间换时间的操作。
前缀和多用于:多次区间求和、子数组计数、滑动窗口优化等,是许多区间题目的基础技能。
答案
思考
(无)