一维前缀和

一、算法思想

前缀和定义：$S_i = a_1 + a_2 + \cdots a_i$。

注意

前缀和下标 $S_i$ 要从 $1$ 开始，从而避免处理边界情况，统一计算 $S_i$。

1.1 计算方法

$S_i = S_{i-1} + a_i$

1.2 作用

$O(1)$ 时间内计算区间 $[l,r]$ 内的元素的和：

$a_l + \cdots a_r = S_r - S_{l - 1}$

二、算法模板

Go

type PrefixSum1D struct {
    sum []int
}

// NewPrefixSum1D 初始化一维前缀和
func NewPrefixSum1D(q []int) *PrefixSum1D {
    n := len(q)
    sum := make([]int, n+1)
    for i := 1; i <= n; i++ {
        sum[i] = sum[i-1] + q[i-1]
    }
    return &PrefixSum1D{sum: sum}
}

// 查询一维前缀和
func (ps *PrefixSum1D) query(l, r int) int {
    return ps.sum[r] - ps.sum[l-1]
}

三、代码实战

AcWing 0795

---

题目：前缀和

输入一个长度为 $n$ 的整数序列。

接下来再输入 $m$ 个询问，每个询问输入一对 $l,r$。

对于每个询问，输出原序列中从第 $l$ 个数到第 $r$ 个数的和。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数数列。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一个询问的区间范围。

输出格式

共 $m$ 行，每行输出一个询问的结果。

数据范围

$1 \le l \le r \le n$

$1 \le n,\ m \le 10^5$

$-1000 \le \text{数列中元素的值} \le 1000$

输入样例：

5 3

2 1 3 6 4

1 2

1 3

2 4

输出样例：

3

6

10

解答代码：

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l - 1]);
    }
    
    return 0;
}

package main

import (
    "bufio"
    . "fmt"
    "io"
    "os"
)

type PrefixSum1D struct {
    sum []int
}

// NewPrefixSum1D 初始化一维前缀和
func NewPrefixSum1D(q []int) *PrefixSum1D {
    n := len(q)
    sum := make([]int, n+1)
    for i := 1; i <= n; i++ {
        sum[i] = sum[i-1] + q[i-1]
    }
    return &PrefixSum1D{sum: sum}
}

// 查询一维前缀和
func (ps *PrefixSum1D) query(l, r int) int {
    return ps.sum[r] - ps.sum[l-1]
}

func run(_r io.Reader, out io.Writer) {
    in := bufio.NewReader(_r)

    var n, m int
    Fscan(in, &n, &m)

    q := make([]int, n)
    for i := 0; i < n; i++ {
        Fscan(in, &q[i])
    }

    ps := NewPrefixSum1D(q)

    for i := 0; i < m; i++ {
        var l, r int
        Fscan(in, &l, &r)
        Fprintf(out, "%d\n", ps.query(l, r))
    }
}

func main() {
    run(os.Stdin, os.Stdout)
}