「数据结构与算法」动静布局学习笔记：前缀和
前缀和是一种查问数组中任意区间的元素的和的数据结构，这里数组给定之后就不变了。针对这个不变的数组，前缀和用于屡次查问区间 [i, j] 上元素的和。
对于动静布局而言，前缀和的意义次要有两点：
- 一维和二维前缀和的推导，别离用到了单串和矩阵中最经典的状态设计以及状态转移
- 在一些更简单的动静布局问题中，状态转移的时候须要依赖区间和，因为状态转移是十分频繁的操作，因而必须高效地求区间和能力使得状态转移的工夫复杂度可承受，此时就必须用到前缀和了
一些问题须要前缀和与其它数据结构配合来解决，也有两类：
- 先预处理出前缀和数组，这一步是动静布局，而后在前缀和数组上用其它数据结构解决
- 还是依照动静布局的形式求前缀和，也须要额定的数据结构保护前缀和，但不是预处理好前缀和数组之后再用数据结构计算，而是每求出一个前缀和，就更新一次数据结构并保护答案
前缀和 简介
给定长度 n 的序列 a (a[0], a[1], ..., a[n-1]) ，给每个前缀求一次和， S[0] = 0 , S[i] = a[0] + a[1] + ... + a[i - 1] 。这些前缀和保护在一个长度 n + 1 数组 S 里，称为前缀和数组。
有两类在数组 a 上的求和需要：
- 前缀和：求
a[0..i]的和 - 区间和：求区间
a[L, R]的和
对于第 1 种前缀和， S[i + 1] 刚好就是答案，因为这就是前缀和的定义。 S[i+1] = a[0] + a[1] + ... + a[i] 。
对于第 2 种区间和，如果曾经有了前缀和数组，两个前缀和 S[R + 1] 和 S[L] 的差刚好就是 [L, R] 上的区间和。已有前缀和数组之后，这一步操作就是 O(1) 的。
定义 sums[k] 为 [0..k-1] 的和，其中 sums[0] 示意数组中没有数字被选中， sums[1] 示意只选中第一个数 nums[0]。 事后计算 0 ~ k (0<=k<=n-1) 的和，这一系列的和都是从 0 开始的，因而称为前缀和。公式如下：
- k = 0:
sum(0, 0) = 0 - 1 <= k <= n:
sum(0, k) = nums[0] + nums[1] + ... + nums[k - 1]
尔后的区间查问都能够利用公式：
sum(i, j) = sums(0, j + 1) - sum(0, i)
线性动静布局中最根底的一种是单串 dp[i] ，并且只与子问题 i - 1 无关，即 dp[i] = f(dp[i-1]) 。前缀和就是这种状况， sums[i] 只与 sums[i-1] 无关。推导前缀和数组的过程是 O(N) 的，如果区间和的查问次数达到了 O(N) 那么计算区间和的工夫复杂度是摊销 O(1) 的。
数据结构 保护 前缀和
用动静布局的形式推 sums[i] 的时候，在某些题型中计算完 sums[i] 后须要查问以前算过的后果以此来计算某种指标（例如小于、大于、等于某个数值等），此时就须要用数据结构来将后面的计算结果保护起来，以便高效查问。
将前缀和保护在数据结构中，以便于后续的屡次查问，最常见的是保护在哈希表 HashMap中。
HashMap 保护 前缀和Key：前缀和（状态）的值Value：第一次呈现时的索引经典问题① a[0], a[1], ..., a[n - 1] 上有没有一个区间，其和为 target
关键词：[有没有]、[区间]、[等于]
计算前缀和数组 sums[i] 。当扫描到 i 时， a[0], a[1], ..., a[i - 1] 的前缀和都曾经求过了，所以能够在计算的过程中，将前缀和保护在数据结构中，以便于后续的屡次查问。本题在之后要查问前缀和的值是否存在，因而保护在HashSet里。
求完以后值 a[i] 对应的前缀和 S[i+1] , 在插入到HashSet之前先思考： S[i+1] - target 在HashSet中是否呈现过。
- 如果呈现：阐明存在以
i结尾的某个区间，和为target，则找到答案 - 如果不呈现：阐明不存在以
i结尾的区间，和为target，则持续枚举i + 1
经典问题② a[0], a[1], ..., a[n - 1] 上有多少个区间，其和为 target
关键词：[多少个]、[区间]、[等于]
整体解题思路与问题①类似。
区别在于题目要求统计个数，所以须要应用HashMap来代替HashSet并以此保护多个 Key（和的值） - Value（该和的值呈现的个数） 键值对。
LeetCode 560 和为 K 的子数组
https://leetcode-cn.com/probl...
经典问题③ a[0], a[1], ..., a[n - 1] 上有多少个区间，其和大于、小于 target
关键词：[多少个]、[区间]、[大于、小于]
LeetCode 327 区间和的个数
https://leetcode-cn.com/probl...
经典问题④ 一棵树上有没有一个门路，其和为 target
关键词：[有没有]、[树]、[等于]
LeetCode 437 门路总和 III
https://leetcode-cn.com/probl...
经典问题⑤ 矩形区域内有多少个子矩阵，其和大于、小于或等于 target
关键词：[有没有]、[多少个]、[矩形区域]、[大于、等于、小于]
LeetCode 363 矩形区域不超过 K 的最大数值和
https://leetcode-cn.com/probl...
LeetCode 1074 元素和为目标值的子矩阵数量
https://leetcode-cn.com/probl...
面试题 17.24 最大子矩阵
https://leetcode-cn.com/probl...
对于矩阵问题，能够优先思考将二维矩阵压缩成一维数组，而后参考问题①②③的形式应用前缀和进行求解。