前缀和计算

前缀和

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。

所用方法和基本原理

1. 前缀和数组的构建：
   • 首先定义了一个方法getPrefixSum来构建前缀和数组。前缀和数组s的作用是记录原数组arr从起始位置到当前位置的所有元素之和。
   • 初始化s[0] = 0，这是因为前缀和从数组的起始位置开始累加，起始位置之前没有元素，和为0。
   • 通过遍历原数组arr，从索引1开始，计算s[m] = s[m - 1] + arr[m]，即当前位置的前缀和等于前一个位置的前缀和加上当前位置的数组元素。这样，前缀和数组s中的每个元素s[i]都表示原数组arr中从arr[0]到arr[i]的所有元素之和。
2. 区间和的计算：
   • 对于每个询问的区间[l, r]，通过已经构建好的前缀和数组s来计算区间和。公式为s[r] - s[l] + arr[l]。
   • s[r]表示从原数组起始位置到位置r的所有元素之和，s[l]表示从原数组起始位置到位置l - 1的所有元素之和（因为前缀和数组的索引从0开始）。所以s[r] - s[l]得到的是从arr[l + 1]到arr[r]的和，再加上arr[l]，就得到了从arr[l]到arr[r]的和。

代码及注释

import java.util.Scanner;

public class RangeSumQuery {
    // 构建前缀和数组
    public static int[] getPrefixSum(int[] arr) {
        int[] s = new int[arr.length];
        s[0] = 0;
        for (int m = 1; m < arr.length; m++) {
            s[m] = s[m - 1] + arr[m];
        }
        return s;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        // 获取前缀和数组
        int[] s = getPrefixSum(arr);
        for (int i = 0; i < m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            // 计算并输出区间和
            int res = s[r] - s[l] + arr[l];
            System.out.println(res);
        }
        sc.close();
    }
}

举例说明

假设原整数序列为arr = [1, 3, 5, 7, 9]，有3个询问，分别为(1, 3)，(0, 2)，(2, 4)。

1. 构建前缀和数组：
   • s[0] = 0。
   • s[1] = s[0] + arr[1] = 0 + 3 = 3。
   • s[2] = s[1] + arr[2] = 3 + 5 = 8。
   • s[3] = s[2] + arr[3] = 8 + 7 = 15。
   • s[4] = s[3] + arr[4] = 15 + 9 = 24。所以前缀和数组s = [0, 3, 8, 15, 24]。
2. 计算询问的区间和：
   • 对于询问(1, 3)：
     • l = 1，r = 3，res = s[3] - s[1] + arr[1] = 15 - 3 + 3 = 15。
   • 对于询问(0, 2)：
     • l = 0，r = 2，res = s[2] - s[0] + arr[0] = 8 - 0 + 1 = 9。
   • 对于询问(2, 4)：
     • l = 2，r = 4，res = s[4] - s[2] + arr[2] = 24 - 8 + 5 = 21。

方法的优劣

1. 时间复杂度：
   • 预处理阶段：构建前缀和数组的时间复杂度为$O(n)$，其中$n$是原数组的长度，因为需要遍历原数组一次。
   • 查询阶段：对于$m$个查询，每个查询的时间复杂度为$O(1)$，因为只需要进行简单的数组访问和加减法运算。所以总的时间复杂度为$O(n+m)$。相比每次查询都遍历区间内所有元素的暴力解法（时间复杂度为$O(m\times n)$），当前方法在处理多个查询时效率有显著提升。
2. 空间复杂度：
   • 需要额外的空间来存储前缀和数组，空间复杂度为$O(n)$，因为前缀和数组的长度与原数组长度相同。

优点：

• 对于多次查询区间和的场景，效率较高，大大降低了时间复杂度。
• 实现相对简单，容易理解和编码。

缺点：

• 需要额外的空间来存储前缀和数组，如果原数组非常大，可能会占用较多内存。
• 当原数组频繁变动时，每次变动后都需要重新计算前缀和数组，维护成本较高。