# 簡介

為了快速計算數列的任意區間總和，可以用此技巧將每次查詢的時間複雜度從 $O(n)$ 降到 $O(1)$。

首先建立兩個陣列：
$a[1 \dots n]$ ： 原始數列
$pre[1 \dots n]$ ： 前綴和陣列

其中前綴和定義為：
$pre[i] = a[1] + a[2] + \cdots + a[i]$

對於任意區間 $[l, r]$，其區間總和為：
$\sum_{i=l}^{r} a[i] = pre[r] - pre[l - 1]$

這樣查詢只需要一次減法，效率高於使用 for 迴圈逐項加總。


# 程式碼

#include<bits/stdc++.h>
using namespace std ;
int a[11] ;
int pre[11] ;
int main(){
    for(int i = 1; i <= 10; i++){
        cin >> a[i - 1];
        pre[i] = pre[i - 1] + a[i - 1] ;  // 計算。
    }
    while(1) {
        int ql , qr ;
        cin >> ql >> qr ;
        cout << pre[qr] - pre[ql-1] << endl ;  // 查詢。
    }
}

# 例題
[a681. B. 吳乙己](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a681)

[a800: 千束開車(1)](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a800)

###### 都看到這了難道不按個愛心支持一下嗎?