一、什么是前缀和前缀和是一种预处理，用于降低查询时的时间复杂度。举个例子：给定n个整数，然后进行m次询问，每次询问求一个区间内值的和。如果用暴力写法，那每次询问都需要从区间左端点循环到区间右端点求和，时间复杂度较大。这种时候就可以预先求出该数组的一维前缀和。则ans=s[R]-s[L-1]，其中L和R是给定的区间。每次询问可直接输出答案，这样时间复杂度就降到了O(N+M)二、前缀和的实现 1、一维前缀和:用数组preSum[i]表示nums的前i项和，i从1开始preSum[i]=preSum[i-1]+nums[i]  一般用于求区间[l,r]的值ans=preSum[r]-preSum[

 一、什么是前缀和前缀和是一种预处理，用于降低查询时的时间复杂度。举个例子：给定n个整数，然后进行m次询问，每次询问求一个区间内值的和。如果用暴力写法，那每次询问都需要从区间左端点循环到区间右端点求和，时间复杂度较大。这种时候就可以预先求出该数组的一维前缀和。则ans=s[R]-s[L-1]，其中L和R是给定的区间。每次询问可直接输出答案，这样时间复杂度就降到了O(N+M)二、前缀和的实现 1、一维前缀和:用数组preSum[i]表示nums的前i项和，i从1开始preSum[i]=preSum[i-1]+nums[i]  一般用于求区间[l,r]的值ans=preSum[r]-preSum[