---
tags: 文華社課
---
> 文華高中電腦研究社29th
> 編輯 : 黃昱凱

# 1-2難題筆記
前綴和預處理
時間複雜度:**O(n * n) -> O(n)**
可以快速計算區間和
初始化 第一項為原值
即pre[1] = a[1] 或 pre[0] = 0
接著每項是前項之和
即pre[i] = pre[i-1] + a[i];

區間[l, r]的值即為
pre[r] - pre[l-1]
## a693:

#include<bits/stdc++.h>
using namespace std;
#define N 100005
    int pre[N] = {0};  //Initialization 
    int a[N];
    int n, m;
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
    }
    pre[0] = 0;
    for(int i = 1;i <= n;i ++){ // fills prefix sum array
        pre[i] = pre[i-1] + a[i];
    }
    for(int i = 0;i < m;i ++){
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l-1] <<endl;
    }
    return 0;
}

## a015
有時候陣列如果讀到範圍以外的值會導致RE
可以稍微開大一點

#include<bits/stdc++.h>
using namespace std;
#define N 105
#define M 105
int main(){
    int n, m;
    while(cin >> n >> m){
        int a[n+5][m+5];//開大一點比較沒問題
        int ans[n+5][m+5];
        for(int i = 0;i < n;i ++){
            for(int j = 0;j < m;j ++){
                cin >> a[i][j];
            }
        }
        swap(n, m);
        for(int i = 0;i < n;i ++){
            for(int j = 0;j < m;j ++){
                ans[i][j] = a[j][i];
                cout << ans[i][j] <<" ";
            }
            cout << endl;
        }
    }
    return 0;
}