前綴和

輸入一個長度為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)$，因為前綴和數組的長度與原數組長度相同。

優點：

• 對于多次查詢區間和的場景，效率較高，大大降低了時間復雜度。
• 實現相對簡單，容易理解和編碼。

缺點：

• 需要額外的空間來存儲前綴和數組，如果原數組非常大，可能會占用較多內存。
• 當原數組頻繁變動時，每次變動后都需要重新計算前綴和數組，維護成本較高。