1.Prefix前缀和【模板】

• [[#题目描述|题目描述]]
• [[#输入描述|输入描述]]
• [[#输出描述|输出描述]]
• [[#输入样例1|输入样例1]]
• [[#输出样例1|输出样例1]]
• [[#暴力穷举|暴力穷举]]
• [[#前缀和数组|前缀和数组]]

题目描述

给定义一个数组a，有q次询问，对于每次询问：

给定两个整数l,r，求出${a_l}$ $+$${a_{l+1}}$ + ${\dots}$ +$a_r$​的结果。

输入描述

第一行一个整数表示样例个数T(1≤T≤10)

对于每组样例：

第一行22个整数n(1≤n≤10^{5),q(1≤q≤10}5)，分别表示数组长度和询问次数。

第二行n个整数，表示数组a(−10^{9≤$a_i$​≤10}9)。

接下来q行，每行两个整数l,r(1≤l≤r≤n)表示询问的区间。

输出描述

对于每组样例，一行一个整数表示答案。

输入样例1

2
5 3
1 2 3 4 5
1 2
2 5
3 4
7 2
-1 9 -10 8 2 6 11
1 5
2 7

输出样例1

3
14
7
8
26

暴力穷举

• 对每一个[l ,r]区间中的数都进行加和
• 使用for循环进行计算
• 最坏情况下n为10的5次方， q为10的5次方，l为1，r为10的5次方
• 总共加和次数为10^10 数量级 对1000ms的数量级而言有点过于高了

前缀和数组

$$P_i = sum_{j=1}^i a_j = P_{i-1} + a_i$$

• 于是便有以下的性质
• 

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 9;
// 全局数组自动初始化为0
ll a[N], prefix[N];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int m;
  cin >> m;
  while (m--) {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) prefix[i] = prefix[i - 1] + a[i];
    while (q--) {
      int l, r;
      cin >> l >> r;
      cout << prefix[r] - prefix[l - 1] << '\n';
    }
  }
  return 0;
}