首页 > 试题广场 >

【模板】前缀和

[编程题]【模板】前缀和

热度指数：22024 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，我们有 $m$ 次查询操作，每一次操作给出两个参数 $l,r$ ，你需要输出数组中第 $l$ 到第 $r$ 个元素之和，即 $a_l + a_{l+1} + \dots + a_r$ 。

输入描述:

第一行输入两个整数  代表数组中的元素数量、查询次数。
第二行输入  个整数  代表初始数组。
此后  行，每行输入两个整数  代表一次查询。

输出描述:

对于每一次查询操作，在一行上输出一个整数，代表区间和。

示例1

输入

输出

3
6

算法知识视频讲解

C++

杨阳阳洋洋

求和之后数据会爆炸，不要用int

发表于 2022-04-03 17:46:42 回复(0)

C++

StellarVibes

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n = 0,q = 0;

cin>>n>>q;

vector<int> arr(n+1);

vector<long long> dp(n+1);

for(int i = 1;i<=n;i++)

cin>>arr[i];

for(int i = 1;i<=n;i++)

dp[i]=dp[i-1]+arr[i];

while(q--)

{

int l = 0,r = 0;

cin>>l>>r;

cout<<dp[r]-dp[l-1]<<endl;

}

return 0;

}

发表于 2025-04-09 19:24:18 回复(1)

C++

木析

前缀和，注意：left和right是从1开始，对应的索引要-1；另外，C++要注意int会越界，需要用long long。

（优化一下的话，nums的数组其实可以不用开。）

#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
int main()
{
    int n,q;
    cin>>n>>q;
    vector<long long> nums(n,0);
    vector<long long> ans(n+1,0); //ans[i]表示nums[0...i-1]之和
    for(int i=0;i<n;++i) {
        cin>>nums[i];
        ans[i+1]+=ans[i]+nums[i];
//         cout<<ans[i+1]<<" ";
    }
//     cout<<endl;
    for(int i=0;i<q;++i) {
        int left, right;
        cin>>left>>right;
        cout<<(ans[right]-ans[left-1])<<endl;
    }
    return 0;
}

发表于 2021-12-25 19:43:37 回复(0)

LH_Coffee

#include <iostream>
#include<vector>
using namespace std;
#define  int long long
signed main() {
    int n,m,num;
    cin>>n>>m;
      vector<int>v(n+1,0);
        v[0]=0;
        for(int i=1;i<=n;i++){
            cin>>v[i];
            v[i]+=v[i-1];
        }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<v[r]-v[l-1]<<endl;
    }
}前缀和顾名思义就是累计求和，这里可以选择开一个数组存储前缀和也可以直接在一个数组里进行边输入数字边累计求和的过程，最后注意求和要开ll

发表于 2026-02-02 17:57:48 回复(0)

cs小白_

#include <stdio.h>

int main() {
    int n,q,a,b;
    long long r;
    scanf("%d %d",&n,&q);
    int c[n+1];
    c[0]=0;
    long long d[n+1];
    d[0]=0;
    for (int i=1; i<n+1; i++) {
         scanf("%d",&c[i]);
         d[i]=d[i-1]+c[i];
    }
    while (q--) {
       
        scanf("%d %d", &a, &b);
         
              r=d[b]-d[a-1];
        
        printf("%lld\n",r);
    }
    
    return 0;
}

发表于 2024-12-01 14:59:15 回复(0)

雪落乾坤

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n,q;
    cin>>n>>q;
    //读入数组
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++) cin>>arr[i];
    //预处理出来一个前缀和数组
    vector<long long> dp(n+1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]+arr[i];
    }
    //使用前缀和数组
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        cout<<dp[b]-dp[a-1]<<endl;
    }
}

发表于 2024-11-03 09:52:22 回复(0)

椰子今天很可爱

//前缀和算法->快速寻找出数组中的某一个连续区间的和

//第一步：创建一个前缀和数组并对齐初始化，dp[i]表示arr数组[1,i]区间上的和

//dp[i] = dp[i - 1] + arr[i]

//注意有些题目是从零开始，需要考虑越界情况

//[l,r]区间的和就是dp[r] - dp[l - 1]

int main() {

long long int arr[100010] ,dp[100010];

arr[0]=0,dp[0]=0;

int n,q;

cin>>n>>q;

for(int i = 1;i <= n;i++)

cin>>arr[i];

for(int i = 1; i<=n;i++)

dp[i]=dp[i-1] + arr[i];

int l ,r;

while(q--)

{

cin>>l>>r;

cout<<dp[r]-dp[l-1]<<endl;

}

return 0;

}

发表于 2024-10-27 23:39:45 回复(0)

__Forever__

前缀和模板：利用一个数组dp记录前n项和，dp[i] 表示前n项的和

注意，i从1开始，是为了处理边界情况，当求原数组[0,2]区间的和是

会有越界情况

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

int main() 
{    
    int n, q; cin >> n >> q;
    vector<int> arr1(n);  //n个整数
    for(int i = 0; i < n; ++i)
        cin >> arr1[i];

    //记录前n项和的数组
    vector<long long> arr2(n + 1, 0);
    for(int i = 0; i < n; ++i)
        arr2[i + 1] = arr2[i] + arr1[i];

    while(q--)
    {
        int l,r;
        cin >> l >> r;
        cout << arr2[r] - arr2[l - 1] << endl;
    }

    return 0;
}

发表于 2024-10-09 17:46:47 回复(0)

吱吱1111111

这道题没给n的范围，很不严谨。n大n小有不同解题思路

发表于 2024-03-21 06:42:24 回复(0)

C++

学个豌豆

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 9;

using ll = long long;

ll a[N],prefix[N];

int main()

{

int n, q; cin >> n >> q;

for(int i = 1;i <= n; ++i) cin >> a[i];

for(int i = 1;i <= n; ++i) prefix[i] = prefix[i - 1] + a[i];

while(q--)

{

int l, r; cin >> l >> r;

cout<<prefix[r] - prefix[l - 1]<<endl;

}

return 0;

}

编辑于 2024-03-15 16:47:01 回复(0)

只是一个小菜鸡

long long

发表于 2023-11-13 22:00:18 回复(0)

C++

senak

#include <iostream>

const int N=1e6;

long long numb[N]={0};

long long prefix[N]={0};

using namespace std;

int main() {

long long n,q;

long long l,r;

cin>>n>>q;

for(int i=1;i<=n;i++)cin>>numb[i];

for(int i=1;i<=n;i++)prefix[i]=prefix[i-1]+numb[i];

while (q--) {

cin>>l>>r;

cout<<prefix[r]-prefix[l-1]<<endl;

}

return 0;

}

发表于 2023-11-11 14:08:28 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var n,q int
    fmt.Scan(&n,&q)
    arr:=make([]int,n+1)
    var x,sum int
    for i:=1;i<=n;i++{
        fmt.Fscan(in,&x)
        sum+=x
        arr[i]=sum
    }
    var l,r int
    for q>0{
        fmt.Fscan(in,&l,&r)
        fmt.Println(arr[r]-arr[l-1])
        q--
    }
}

发表于 2023-02-24 21:26:35 回复(0)

柠檬汽水儿

#include <stdio.h>

int main() {
    long long n,q;
    long long *p1;
    scanf("%d%d",&n,&q);
    long long arr[1000];
    long long brr[100];
    p1=arr;
    for(int i=0;i<n;i++){
        scanf("%lld",&arr[i]);
    }
    long long a,b;
    long long t=0;
    while(q){
        scanf("%lld%lld",&a,&b);
        long long sum=0;
        for(int i=a-1;i<b;i++){
            sum+=*(p1+i);
        }
        brr[t++]=sum;
        q--;
    }
    for(int i=0;i<t;i++){
        printf("%lld\n",brr[i]);
    }
    return 0;
}我这段代码为什么有些样例通不过，求解

发表于 2022-12-03 17:46:56 回复(0)

Java

牛客208400313号

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }

        // 前缀和数组（分开写便于理解），int[]会溢出
        long[] preSum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        // 计算区间和
        for (int i = 0; i < q; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            System.out.println(preSum[r] - preSum[l - 1]);
        }
    }
}

发表于 2022-10-05 08:59:55 回复(0)

C/C++

牛客382637577号

vector还没弄明白，先用普通数组吧

#include<iostream>

using namespace std;

const int N = 100010;

int q,n;
long long a[N],s[N];//设a数组为原数组，s数组为前缀和数组

int main(){

	scanf("%lld%d", &n, &q);

	for( int i =1; i <=n;i++)   scanf("%lld",&a[i]);//初始化数组
	for( int i=1;i<= n; i++) s[i] = s[i- 1] +a[i];
    while(q--){
        int l,r;
    cin>>l>>r;
        cout<<s[r] - s[l-1]<<endl;
    }
return 0;
}

发表于 2022-09-12 10:09:42 回复(1)

Python 3

Kiron_L

def solution(nums):
    res = [0] * len(nums)
    res[0] = nums[0]
    for i in range(1, len(nums)):
        res[i] = res[i - 1] + nums[i]
    return res


n, q = map(int, input().split())
nums = list(map(int, input().split()))
res = solution(nums)
for i in range(q):
    l, r = map(int, input().split())
    if l == 1:
        print(res[r - 1])
    else:
        print(res[r - 1] - res[l - 2])

发表于 2022-08-17 00:41:20 回复(0)

C++

淡念余安

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

vector<long> solve(vector<int>& a, vector<pair<int, int>>& query)
{
    int n = a.size();
    vector<long> dp(n + 1);
    dp[0] = 0;
    for(int i = 1; i < n + 1; i++)
    {
        dp[i] = dp[i - 1] + a[i - 1];
    }
    vector<long> res;
    for(int i = 0; i < query.size(); i++)
    {
        int right = query[i].second;
        int left = query[i].first;
        long tmp = dp[right] - dp[left - 1];
        res.push_back(tmp);
    }
    return res;
}

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> a;
    vector<long> res;
    for(int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        a.push_back(num);
    }
    vector<pair<int, int>> query;
    for(int i = 0; i < q; i++)
    {
        int left, right;
        cin >> left >> right;
        query.push_back({left, right});
    }
    res = solve(a, query);
    for(int i = 0; i < res.size(); i++)
    {
        cout << res[i] << endl;
    }
    return 0;
}

发表于 2022-07-06 21:27:51 回复(0)

srcrs

这是看不起go啊，大概率过不了，小概率能过

package main

import "fmt"

func main() {
	var n, q int
	fmt.Scanln(&n, &q)
	arr := make([]int64, n+2)
	for i := 1; i <= n; i++ {
		fmt.Scanf("%d", &arr[i])
		arr[i] = arr[i] + arr[i-1]
	}
	for i := 0; i < q; i++ {
		var l, r int
		fmt.Scanln(&l, &r)
		fmt.Println(arr[r] - arr[l-1])
	}
}

发表于 2022-05-07 22:34:49 回复(0)

C++

元气少女李逵

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    long long n,q;
    cin>>n>>q;
    vector<long long> a;
    for(long long i=0;i<n;i++)
    {
        long long b;
        cin>>b;
        a.push_back(b);
    }
//要先算前n项和，不然会超时
    vector<long long> dp(n+1,0);
    for(long long i=0;i<n;i++)
    {
        dp[i+1]=dp[i]+a[i];
    }
    while(q)
    {
        long long count=0;
        long long l,r;
        cin>>l>>r;
        count=dp[r]-dp[l-1];
        cout<<count<<endl;
        q--;
    }
    return 0;
}

发表于 2022-04-14 14:41:16 回复(0)