【模板】静态区间和（前缀和）

思路

拿到这道题，先想一下：给你一个数组，反复查询某一段区间的和，暴力做法每次查询都遍历一遍区间，时间复杂度 ，数据量 级别直接超时。有没有办法把每次查询优化到 ？

这就是前缀和的经典应用场景了。

什么是前缀和？

前缀和数组 pre[i] 表示原数组前 i 个元素的累加和。构建方式很简单：

$$

其中 ，作为边界。

怎么用前缀和求区间和？

想求区间 的和，直接用：

$$

为什么？你画个图就明白了： 是前 个元素的总和， 是前 个元素的总和，两者一减，剩下的不就是第 到第 个元素的和吗？

有什么坑？

这题元素范围是 ，数组长度最大 ，前缀和最大能到 级别，int 会爆，必须用 long long。

代码

#include <cstdio>
using namespace std;

long long pre[1000001];

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

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        long[] pre = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + Long.parseLong(st.nextToken());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            sb.append(pre[r] - pre[l - 1]).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]
    out = []
    for _ in range(m):
        l, r = map(int, input().split())
        out.append(str(pre[r] - pre[l - 1]))
    sys.stdout.write('\n'.join(out) + '\n')

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const [n, m] = lines[idx++].split(' ').map(Number);
    const a = lines[idx++].split(' ').map(Number);
    const pre = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }
    const out = [];
    for (let i = 0; i < m; i++) {
        const [l, r] = lines[idx++].split(' ').map(Number);
        out.push(pre[r] - pre[l - 1]);
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度：，预处理前缀和 ，每次查询 ，共 次查询
  • 空间复杂度：，存储前缀和数组

总结

前缀和是处理静态区间查询的基本功，核心就两步：建前缀和数组、用减法算区间和。这题本身不难，但一定要注意数据类型用 long long，不然就是白送的 WA。Java 那边注意用 BufferedReader 读入，Scanner 在大数据量下容易超时。