前缀和

一维前缀和

https://www.papamelon.com/post/5xQHCbo6U6UGizt7g1figiEHYkp3j9e9
问题描述：
1.长度为$N$的一维数组$a[N]$
2.$Q$个询问，每次询问$[L,R]$这段区间的区间和是多少？
问题解决：区间和等于两个前缀和的差值
Note:在前缀和问题中，数组下标可以选择从1开始

首先，定义s[i]=a[1]+a[2]+a[3]+···a[i]
容易发现a[L~R]=s[R]-s[L-1]
递推公式：s[i]=s[i-1]+s[i]
时间复杂度：$O(N+Q)$
例题：
leetcode 724. 寻找数组的中心索引
例题
例题分析：
左半部分s[l]=s[index-1]
右半部分s[r]=s[n]-s[index]
枚举:$O(N)$
前缀和预处理:$O(1)$
总时间复杂度：$O(N)$

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n=nums.size();
        //预处理前缀和数组
        //一般数组0下标开始：1下标比较容易实现
        //s[1]~s[n];
        vector<int> s(n+1);//默认为0
        //根据递推公式构造前缀和数组
        for(int i=1;i<=n;i++)
            s[i]=s[i-1]+nums[i-1];//注意下标问题
        int index = -1;
        //枚举中心索引
        //判断是否正确
        for(int i=0;i<n;i++)
        {
            int sl=s[i];//左端的和nums[0]~nums[i-1]=s[i]
            int sr=s[n]-s[i+1];//nums[i+1]~nums[n-1]=s[n]-s[i+1]
            if(sl==sr)
            {
                index=i;
                break;
            }
        }
        return index;
    }
};