前言
对于一个数组,为了快速求 [L,R]
内的和,引入前缀和概念,求静态数组内的和
前缀和:从第一个数 到 当前位置 的 总和
普通数组
S0 = 0
S1 = a1;
Sn = a1 + a2 + … + an;
前缀和数组 :开一个数组专门记录前缀和
Si = Si-1 + ai
因此,求[L,R]
内的和
SLR = SR - SL-1
模板题 795. 前缀和
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N];//正常数组 记录输入的序列 int s[N];// 前缀和数组 int n, m; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); s[i] = s[i - 1] + a[i]; } for (int i = 0; i < m; i++) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", s[r] - s[l - 1]); } return 0; }
796. 子矩阵的和
99. 激光炸弹
1230. K倍区间