前缀和，简单直观的理解即是数列A的前i项和。其数学式为
。
在二维数组上，前缀和同样有其用武之地：
。
一、初步了解到什么是前缀和之后，另一个问题很自然而然就跳出来了——“前缀和有什么用？”或者说“前缀和有什么优势？”
? ? ? ? 其实前缀和的作用也仅是查询罢了。假设给你一个长为n的数组，接下来会有m个人对你提问，每个人都会给你l、r两个数，要求你回答从A[l]到A[r]的所有元素和，即：
? ? ? ? 这个问题其实也不难，大不了每问一次你就做一次加法，时间复杂度也不过O(mn)【好像还挺小的】。
while(m--){
for(int i=l;i<=r;i++){
ans+=a[i];
}
}? ? ? ? 但是如果我告诉你这个数组长度只有n=100，但是有10^7个人来提问。
? ? ? ? 这个时候你会感觉有点不对劲，毕竟当l<=100 && r<=100时，问题种类也就10000左右，这意味着你要回答很多重复的问题。
? ? ? ? 打表！是的，前缀和就是一种打表。
? ? ? ? 在经过简单的O(n)时间处理，你就可以用O(1)的时间回答每个问题。即总的时间复杂度为O(m+n)。
for(int i=1;i<=n;i++)
s[i]=s[i-1]+a[i];
while(m--)
ans=s[r]-s[l-1];? ? ? ? 你甚至不需要额外的O(n)空间，完全可以用A[i]+=A[i-1]在A数组的内存上操作。
二、当然这并不意味这前缀和的题目仅此而已了。
? ? ? ? 一道优秀的前缀和问题往往会叠加上排序、思维、贪心、二分、离散化以及包括但不限于排列组合、容斥原理、矩阵运算等数学原理之类的知识点。关于这部分进阶的题目可以在【前缀和_CCPC/ICPC区域赛知识点练习_牛客竞赛OJ】 (nowcoder.com)题集中好好探索一番。
