# 前綴 prefix

## infro
前綴是一種資料型態，只要先預處理就可以，用更快的速度計算數列的區間和
只要是可以恢復的運算都可以用前綴，像+、$\times$、xor
前墜儲存和的就叫前墜和

## 原理
開兩個陣列a[]和pre[]，a儲存原數列，pre儲存前墜和數列
pre[n] = a[0] + a[1] + a[2] + ... + a[n]
pre[i] - pre[j - 1] = a[j] + a[j + 1] + a[j + 2] + ... + a[i]
平常我們查詢長度為n的數列的區間和時，我們要用for跑n次
而我們用前綴和，就可以只用這一次減法計算

## 預處理
預處理的方法就是每輸入一個就維護一次前綴和
也就是當我輸入a[i]
那我就更新pre[i]，而pre[i] = pre[i - 1] + a[i];

要特別注意，在輸入第一個時要小心取pre[i-1]時不要讓i-1變成負的

for(int i = 1; i <= n; i++){
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
}

## 查詢
查詢就是pre[qr] -pre[ql - 1]

## 綜合

#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];
        pre[i] = pre[i - 1] + a[i];
    }
    while(1){
        int ql, qr;
        cin >> ql >> qr;
        cout << pre[qr] - pre[ql - 1] << '\n';
    }
}

## 練習題
[dandanjudge a681](http://203.64.191.163/ShowProblem?problemid=a681)
[dandanjudge a800](http://203.64.191.163/ShowProblem?problemid=a800)