范圍總和查詢，無更新 · GeeksForGeeks 中文系列教程

# 范圍總和查詢，無更新 > 原文： [https://www.geeksforgeeks.org/range-sum-queries-without-updates/](https://www.geeksforgeeks.org/range-sum-queries-without-updates/) 給定大小為 n 的整數的數組 arr。我們需要計算從索引 i 到索引 j 的元素總和。由 i 和 j 索引值組成的查詢將被多次執行。例子： ``` Input : arr[] = {1, 2, 3, 4, 5} i = 1, j = 3 i = 2, j = 4 Output : 9 12 Input : arr[] = {1, 2, 3, 4, 5} i = 0, j = 4 i = 1, j = 2 Output : 15 5 ``` **簡單解決方案**是為每個查詢計算總和。一種有效的**解決方案**是預先計算前綴和。令 pre [i]存儲從 arr [0]到 arr [i]的元素之和。為了回答查詢（i，j），我們返回 pre [j] – pre [i-1]。 ## CPP ``` // CPP program to find sum between two indexes // when there is no update. #include <bits/stdc++.h> using namespace std; void preCompute(int arr[], int n, int pre[]) {? ????pre[0] = arr[0]; ????for (int i = 1; i < n; i++)? ????????pre[i] = arr[i] + pre[i - 1];???? } // Returns sum of elements in arr[i..j] // It is assumed that i <= j int rangeSum(int i, int j, int pre[]) { ????if (i == 0) ???????return pre[j]; ????return pre[j] - pre[i-1]; } // Driver code int main() { ????int arr[] = { 1, 2, 3, 4, 5 }; ????int n = sizeof(arr)/sizeof(arr[0]); ????int pre[n]; ????preCompute(arr, n, pre); ????cout << rangeSum(1, 3, pre) << endl; ????cout << rangeSum(2, 4, pre) << endl;???? ????return 0; } ``` ## Python3 ```py # Python program to find sum between two indexes # when there is no update. def find_ans(ar, j, k): ????l = len(ar) ????for i in range(1, l): ????????ar[i] = ar[i] + ar[i-1] ????print(ar[k] - ar[j-1]) ????return;? pr = [1, 2, 3 ,4, 5] ar = pr[:] find_ans(ar, 1, 3) ar = pr[:] find_ans(ar, 2 ,4) # Code Contributed by Mohit Gupta_OMG <(0_o)> ``` ## Java ```java // Java program to find sum between two indexes // when there is no update. import java.util.*; import java.lang.*; class GFG { ????public static void preCompute(int arr[], int n, int pre[]) ????{ ????????pre[0] = arr[0]; ????????for (int i = 1; i < n; i++) ????????????pre[i] = arr[i] + pre[i - 1]; ????} ????// Returns sum of elements in arr[i..j] ????// It is assumed that i <= j ????public static int rangeSum(int i, int j, int pre[]) ????{ ????????if (i == 0) ????????????return pre[j]; ????????return pre[j] - pre[i-1]; ????} ????public static void main(String[] args) ????{ ????????int arr[] = { 1, 2, 3, 4, 5 }; ????????int n = arr.length; ????????int pre[] = new int[n]; ????????preCompute(arr, n, pre); ????????System.out.println(rangeSum(1, 3, pre)); ????????System.out.println(rangeSum(2, 4, pre)); ????} } // Code Contributed by Mohit Gupta_OMG <(0_o)> ``` ## C# ```cs // Program to find sum between two // indexes when there is no update. using System; class GFG { ????public static void preCompute(int[] arr, int n, int[] pre) ????{ ????????pre[0] = arr[0]; ????????for (int i = 1; i < n; i++) ????????????pre[i] = arr[i] + pre[i - 1]; ????} ????// Returns sum of elements in ????// arr[i..j] ????// It is assumed that i <= j ????public static int rangeSum(int i, int j, int[] pre) ????{ ????????if (i == 0) ????????????return pre[j]; ????????return pre[j] - pre[i - 1]; ????} ????// Driver code ????public static void Main() ????{ ????????int[] arr = { 1, 2, 3, 4, 5 }; ????????int n = arr.Length; ????????int[] pre = new int[n]; ????????preCompute(arr, n, pre); ????????Console.WriteLine(rangeSum(1, 3, pre)); ????????Console.WriteLine(rangeSum(2, 4, pre)); ????} } // Code Contributed by Anant Agarwal. ``` **輸出**： ``` 9 12 ``` 在這里，每個范圍總和查詢的時間復雜度為`O(1)`。當還允許更新時，問題變得復雜。在這種情況下，請使用高級數據結構，例如[段樹](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/)或[二進制索引樹](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)。本文由 [**Rahul Chawla**](https://www.linkedin.com/in/rahulchawla1995/) 提供。如果您喜歡 GeeksforGeeks 并希望做出貢獻，還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 或郵件撰寫文章您的文章為 commit@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。