洛谷:P78218:求区间和


洛谷:P78218:求区间和

题目

P8218:求区间和

分析

前缀和是一个重要的概念,需要牢牢掌握。本题是入门题,旨在帮助学生掌握这个基本概念和应用。

前缀和概念和应用

前缀和(prefix sum)用于快速计算数组任意区间的和。设数组为a,构造前缀和数组s

s[i] = a[1] + a[2] + ...... + a[i] //(常用 1-based)。  

则任意区间[l, r]的和为:sum(l, r) = s[r] - s[l - 1]

显然,有了前缀和数组后,在求任意一个区间和的时候,只要进行一次加法操作,而代价只是多了一个存放前缀和数组的空间——典型的以空间换时间的操作。

前缀和多用于:多次区间求和、子数组计数、滑动窗口优化等,是许多区间题目的基础技能。

答案

Solution

思考

(无)

Next