DP34 前缀和

一、题目

二、最初暴力算法，时间复杂度过高

注意溢出问题

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,q;
    cin>>n>>q;
    vector<long long>data;
    for(int i =0 ;i<n;i++)
    {
        int x;
        cin>>x;
        data.push_back(x);
    }
    long long sum =0;
    for(int i=0;i<data.size();i++)
    {
        sum+=data[i];
    }
    vector<long long>ret;
    for(int i = 0;i<q;i++)
    {
            int left,right;
            cin>>left>>right;
            if(left == right)
            {
                ret.push_back(data[left-1]);
            }
            else
            {
                long long sum1=0, sum2=0;
                for(int a =0;a<left-1;a++)
                {
                    sum1+=data[a];
                }
                for(int b =right;b<data.size();b++)
                {
                    sum2+=data[b];
                }
                ret.push_back(sum-sum1-sum2);
               
            }  
    }
   
    vector<long long>::iterator it = ret.begin();
    while(it!=ret.end())
    {
        cout<<*it<<endl;
        it++;
    }
   
    return 0;
}
//  位输出请用 printf("%lld")

三、改进

• 使用动态规划dp数组，dp[i]存放从0到下标为i的数组的和

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,q;
    cin>>n>>q;
    vector<long long>data;
    for(int i =0 ;i<n;i++)
    {
        int x;
        cin>>x;
        data.push_back(x);
    }
    vector<long long>dp(n,0);//从0到该下标的和
    dp[0] = data[0];
    dp[1] = data[1]+data[0];
    for(int i=0;i<data.size();i++)
    {
        dp[i]=dp[i-1]+data[i];
    }
    vector<long long>ret;
    for(int i = 0;i<q;i++)
    {
            int left,right;
            cin>>left>>right;
            if(left == right)
            {
                ret.push_back(data[left-1]);
            }
            else
            {
                ret.push_back(dp[right-1]-dp[left-2]);
               
            }  
    }
   
    vector<long long>::iterator it = ret.begin();
    while(it!=ret.end())
    {
        cout<<*it<<endl;
        it++;
    }
   
    return 0;
}
//  位输出请用 printf("%lld")