对于长度为的数列。
定义他的前缀和为。
如果需要获得数组的一部分的和，可以直接通过前缀和相减得到
定义他的差分为。
如果需要修改一个区间的值，那么可以只修改和
对于二维情况和高维情况可以类似定义前缀和
可以用容斥的方法
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; } }
也可以先每一行求前缀和，再每一列求前缀和。
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] += a[i][j - 1]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] += a[i - 1][j]; } }
初始
1 2 4
8 16 32
64 128 256
每一行前缀和
1 3 7
8 24 56
64 192 448
每一列前缀和
1 3 7
9 27 63
73 219 511
## m次前缀和
初始数组第x项 $a_x$
一次前缀和的第x项
$$\sum_{1 \leq i \leq x} a_i$$
二次前缀和的第x项
$$\sum_{1 \leq i \leq x} \sum_{1 \leq j \leq i} a_j = \sum_{1 \leq k \leq x} \sum_{k \leq j \leq i \leq x}a_k = \sum_{1 \leq j \leq x} (x - j + 1) a_j$$
三次前缀和的第x项
$$\sum_{1 \leq i \leq x} \sum_{1 \leq j \leq i} \sum_{1 \leq k \leq j}a_k = \sum_{1 \leq j \leq x} \sum_{j \leq i \leq x}a_j = \sum_{1 \leq j \leq x} \binom{x - j + 2}{2} a_j$$
m次前缀和的第x项
$$\sum_{1 \leq j \leq x} \binom{x - j + m - 1}{m - 1} a_j$$
$$\sum_{1 \leq j \leq x} \sum_{0 \leq k < m} \binom{x + m - 1}{m - 1 - k} \binom{- j}{k} a_j$$
即使 n 和 m 是负数，也是可以使用的
$$\binom{n + m}{l} = \sum_{0 \leq k \leq l} \binom{n}{k} \binom{m}{l - k}$$
## 关于自然数次幂和的讨论
https://en.wikipedia.org/wiki/Faulhaber%27s_formula
1到n的m次方和 mod 10007
mod的数字很小，有循环节
(1**m + ... + 10007 **m) % 10007 暴力
n % 10007的答案 + n / 10007 * 循环节
(1**m + ... + 10007 **m) % 10007 在绝大多数情况下是0
例外 m = 10006的时候
## 参考题目
[Luogu P1314](https://www.luogu.org/problemnew/show/P1314)
二分$W$，然后计算前缀中满足$w_j \geq W$的个数和$v_j$之和。
[Luogu P1969](https://www.luogu.org/problemnew/show/P1969)
[Luogu P5019](https://www.luogu.org/problemnew/show/P5019)
差分，求出所有正数之和（同时也是负数之和的相反数），即为答案。
[Luogu P4552](https://www.luogu.org/problemnew/show/P4552)
差分，求出所有正数之和（同时也是负数之和的相反数），即为第一问答案。
第二问答案为第一个数字和最后一个数字之差：`abs(a[1] - a[n])`
[Luogu P2213](https://www.luogu.org/problemnew/show/P2213)
$(i, j)$映射到$(i + j, i - j + n)$，然后每次询问是一个矩形区域，二维部分和。
## 参考资料
https://en.wikipedia.org/wiki/Prefix_sum
# 前缀和
### CF816B Karen and Coffee
https://codeforces.com/contest/816/problem/B
a[1] a[2] a[3] a[4]
b[i] = b[i-1] + a[i]
b[0] = 0
b[1] = a[1]
b[2] = a[1] + a[2]
b[3] = a[1] + a[2] + a[3]
b[4] = a[1] + a[2] + a[3] + a[4]
b[5] = a[1] + a[2] + a[3] + a[4] + a[5]
b[i] = a[1] + a[2] + ... + a[i]
如果a数组，输入之后不再改变
求前缀和
a[l] + a[l+1] + ... + a[r]的和 = b[r] - b[l - 1]
差分
b[i] = a[i] - a[i-1]
希望b[l], b[l+1], ..., b[r]增加 += 1
那么只需要改 a 数组中的两项
a[l] += 1
a[r + 1] -= 1
https://www.luogu.com.cn/problem/P1865
前缀和，质数个数
树状数组
f[i] 以a[i]结尾的最大的一段的和
f[i] = a[i] + max(0, f[i-1])
用前缀和解决最大子段和
b[i] - min(b[0], b[1], b[2], ..., b[i-1])
有若干个操作
每个操作(s, t, d)
a[s] += d
a[s+1] += d
...
a[t] += d
区间 += d
最后询问每个位置的值（和初始，能提供的教室个数比较）
区间 += d
等价于在差分数组中，修改2个位置。
b[i] = a[i] - a[i-1]
b[s] += d;
b[t + 1] -= d;
非常适合，先修改，最后一起询问
（先修改差分数组，求前缀和，最后一起回答所有答案）
prefix sum and difference
s[i] = a[1] + a[2] + .. + a[i] = s[i-1] + a[i]
b[i] = a[i] - a[i-1]
interval change
point query
1. change l, r, x. a[l] += x, a[l+1] += x, ... , a[r] += x;
2. query x; return x
interval change only changes 2 positions of the difference array
a[l] += x, a[l+1] += x, ... , a[r] += x;
b[l] += x; b[r+1] -= x; // only 2 positions
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 0 0 a
diff 0 0 1 0 0 0 -1 0 0 0 b
### P1083 借教室
借教室，微小的优化
如果前mid个可以
left = mid
如果前mid个不可以
right = mid
前mid个可以之后
直接将初始数组 -= 前mid个操作需要的数量
之后判断只需要从从mid+1开始做就可以了。
时刻保持
calc(L) <= s
calc(R) > s
L == R-1
### P1314 聪明的质监员
直接二分权值，范围1到1000000
将所有权值排序，再二分
找到
s[l] == s[r]
r - l最大值是多少
对于每个值x，计算出s[l]==x最小的l是多少。
### P1114 “非常男女”计划
```cpp
# include <bits/stdc++.h>
<p class="mume-header " id="include-bitsstdch"></p>
using namespace std;
int l[200010],ans,n;
int main()
{
cin>>n;
int t = n;
memset(l, -1, sizeof l);
l[0] = 0;
for (int i=1;i<=n;i++){
int x; cin>>x;
if (x == 0)
{
t++;
}
else
{
t--;
}
if (l[t] == -1)
{
l[t] = i;
}
ans = max(ans, i - l[t]);
}
cout<<ans<<endl;
return 0;
}
(s[r] - s[l]) % 7 = (a[l + 1] + a[l + 2] + .. + a[r]) % 7 == 0
欧拉筛法 O(n)
埃拉托斯特尼筛法 O(n log log n) = O(n * (1/2 + 1/3 + 1/5 + 1/7 + ...))
排序，或者 map<vector
二维和高维前缀和
a[1 .. n][1 .. m]
询问
b[i][j] = sum(a[1 .. i][1 .. j])
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a[i][j]
}
}
等价于
每一行求前缀和
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { b[i][j] = b[i][j - 1] + a[i][j]; // a[i][j] += a[i][j - 1]; } }
每一列求前缀和
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { b[i][j] += b[i - 1][j]; // a[i][j] += a[i - 1][j]; } }
3维情况
a[1 .. n][1 .. m][1 .. l] for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int k = 1; k <= l; k++) { b[i][j][k] = sum(a[1 .. i][1 .. j][1 .. k]) b[i][j][k] = b[i][j][k-1] + b[i][j-1][k] + b[i-1][j][k] - b[i][j-1][k-1] - b[i-1][j][k-1] - b[i-1][j-1][k] + b[i-1][j-1][k-1] + a[i][j][k] } } }
非常麻烦
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int k = 1; k <= l; k++)
{
a[i][j][k] += a[i][j][k - 1];
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int k = 1; k <= l; k++)
{
a[i][j][k] += a[i][j - 1][k];
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int k = 1; k <= l; k++)
{
a[i][j][k] += a[i - 1][j][k];
}
}
}
分别对每一维求前缀和
if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
如果没有n的限制怎么做呢？
有O(R*C*C)的做法
修改单点，询问区间
修改区间，询问单点
一般认为前者简单
贪心，按照花费从大到小排序
交换相邻2个不会更优，所以排序就是最优解
区间 减一
s0 = 0次方之和（等价于 个数
s1 = 1次方之和
s2 = 2次方之和
s3 = 3次方之和
ans = s1 * s1 * s1 - 3 * s2 * s1 + 2 * s3
单调队列
f[i][j] 前i个村庄，建j个学校最小代价
快速求出一个区间的最小代价
带权值的中位数
https://www.spoj.com/problems/ADARAINB/
@import "problems/arc078_a.md"