前缀和怎么做区间求和：原理与 Java 写法

处理数组区间查询时，前缀和是最省事的那种优化。数组只扫一遍，后面的每次查询都能把时间压到 O(1)。数据量一大，这个差别就很明显了。

问题描述

给定一个长度为 n 的整数数组 a，以及 m 次查询。每次查询给出两个参数 l 和 r，要求输出第 l 个到第 r 个元素之和，也就是 a[l] + ... + a[r]。

输入格式：

第一行包含两个整数 n, m (1 ≤ n, m ≤ 10^5)
第二行包含 n 个整数 a[1]...a[n] (-10^9 ≤ a[i] ≤ 10^9)
接下来 m 行，每行两个整数 l, r (1 ≤ l ≤ r ≤ n)

输出格式：

对于每次查询，输出一行整数表示区间和。

示例： 输入：

输出：

3
6

核心思路

直接对每个查询从头累加，最坏情况会把 m 次查询都拉成线性复杂度。n 和 m 都到 10^5 时，这种做法基本就不够用了。

前缀和的做法更像是先做一张'累计表'。我们先算出数组 dp，其中 dp[i] 表示原数组从下标 1 到 i 的元素总和。

公式只有一条：

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

有了这张表，区间 [l, r] 的和就能直接算：

sum(l, r) = dp[r] - dp[l - 1]

这个思路的关键不是'算得快'，而是把重复的部分提前算掉。查询多的时候，收益很直接。

需要留意的点

索引从 1 开始更顺手：前缀和数组通常开成 n + 1，并且令 dp[0] = 0。这样 l = 1 时也不用特判。
别用 int 硬扛总和：单个元素最大到 10^9，累加后很容易超过 32 位整数范围，前缀和数组要用 long。

代码实现

下面这份 Java 代码按题意完成了输入、前缀和构建和区间查询。这里保留了 Scanner，写法直观，适合看思路；如果是更严苛的输入环境，通常会换成更快的读入方式。

import java.util.Scanner;

public class Main {
    public    {
            (System.in);
        
         (!in.hasNextInt()) ;
           in.nextInt();
           in.nextInt();
        
        [] array =  [n + ];
         (   ; i <= n; i++) {
            array[i] = in.nextInt();
        }
        
        [] dp =  [n + ];
         (   ; i <= n; i++) {
            dp[i] = dp[i - ] + array[i];
        }
        
         (m > ) {
               in.nextInt();
               in.nextInt();
            System.out.println(dp[r] - dp[l - ]);
            m--;
        }
        
        in.close();
    }
}

前缀和怎么做区间求和：原理与 Java 写法