2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和 [2020/05/31 22:24] admin update |
2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和 [2020/06/03 09:20] (当前版本) shaco |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | **格式**： | ||
| - | |||
| - | - 第二层标题建议改为二级标题（5个 ''=''） | ||
| - | - 行间公式建议使用 ''$$ $$'' 包裹，而不是 ''\[\]'' | ||
| - | - 三维前缀和的三个公式建议分三行较为美观 | ||
| - | |||
| - | **内容**：例题中涉及到了不定维数的前缀和，可否拿出来单独讲一下？ | ||
| - | |||
| ====== 前缀和 ====== | ====== 前缀和 ====== | ||
| 一些情况下，对数组的子区间和进行多次询问，遍历是一个费时的行为，前缀和在这里就很有用。 | 一些情况下，对数组的子区间和进行多次询问，遍历是一个费时的行为，前缀和在这里就很有用。 | ||
| - | ==== 多维前缀和 ==== | + | ===== 多维前缀和 ===== |
| {{:2020-2021:teams:no_morning_training:1.png?400|}}\\ | {{:2020-2021:teams:no_morning_training:1.png?400|}}\\ | ||
| 行 47: | 行 39: | ||
| </code> | </code> | ||
| - | \[ a_1[i][j][k]=\sum_{l=1}^i {a[l][j][k]}\quad a_2[i][j][k]=\sum_{l=1}^j {a_1[i][l][k]}\quad a_3[i][j][k]=\sum_{l=1}^k {a_2[i][j][l]}\] | + | $$a_1[i][j][k]=\sum_{l=1}^i {a[l][j][k]}$$ |
| + | $$a_2[i][j][k]=\sum_{l=1}^j {a_1[i][l][k]}$$ | ||
| + | $$a_3[i][j][k]=\sum_{l=1}^k {a_2[i][j][l]}$$ | ||
| a3数组即为所求，更高维度同理\\ | a3数组即为所求，更高维度同理\\ | ||
| 就是说按维每一维加一遍。这样做可以将复杂度降至$O(n^t\times t)$。维数较高的情况下会节省一些时间。 | 就是说按维每一维加一遍。这样做可以将复杂度降至$O(n^t\times t)$。维数较高的情况下会节省一些时间。 | ||
| - | === 例子 === | + | ==== 例子 ==== |
| - | == 1. == | + | === 1. === |
| 数字列表项目给定一个 $n\times n$ 的矩阵，找一个最大的子矩阵，使得这个子矩阵里面的元素和最大。 | 数字列表项目给定一个 $n\times n$ 的矩阵，找一个最大的子矩阵，使得这个子矩阵里面的元素和最大。 | ||
| 行 58: | 行 52: | ||
| 好一点的想法是枚举上下边，中间的矩阵就成了一维数列，变成求最大区间和的问题，达到 $O(n^3)$ 。 | 好一点的想法是枚举上下边，中间的矩阵就成了一维数列，变成求最大区间和的问题，达到 $O(n^3)$ 。 | ||
| - | == 2. == | + | === 2. === |
| 输入一个长度为n的数组a[i]，下标从0开始（0到n-1）。保证n是2的整数次幂，对于每个 $i(0\le i<n)$ 求所有满足 ''i&j=j'' 的a[j]之和。$n\le2^{20}$ 。 | 输入一个长度为n的数组a[i]，下标从0开始（0到n-1）。保证n是2的整数次幂，对于每个 $i(0\le i<n)$ 求所有满足 ''i&j=j'' 的a[j]之和。$n\le2^{20}$ 。 | ||
| 例如 $n=2^{10}$ ，就可以将每一个i根据2进制形式视作具有10维，所求即为其前缀和。利用上面所说的方法容易实现。 | 例如 $n=2^{10}$ ，就可以将每一个i根据2进制形式视作具有10维，所求即为其前缀和。利用上面所说的方法容易实现。 | ||
| - | 这个题是付费题目所以....还是贴一下链接 [[https://ac.nowcoder.com/acm/contest/167/C?&headNav=acm|ouo]] | + | （这里让我说一下不定维数的前缀和，不过我在网上没有搜到相关内容，就说一说我的理解。就如同这个题，数据确定维数，那么就不用拘泥于正常的数组的方式，用自己所理解的方式明确数组的下标，进行前缀和的计算即可。） |
| + | [[https://ac.nowcoder.com/acm/contest/167/C?&headNav=acm|链接]] | ||
| <hidden 代码> | <hidden 代码> | ||
| 行 92: | 行 87: | ||
| </hidden> | </hidden> | ||
| ---- | ---- | ||
| - | ==== 总结 ==== | + | ===== 总结 ===== |
| 一个基础技巧。 | 一个基础技巧。 | ||
| - | ==== 参考 ==== | + | ===== 参考 ===== |
| [[https://www.cnblogs.com/mrclr/p/8423136.html]]\\ | [[https://www.cnblogs.com/mrclr/p/8423136.html]]\\ | ||
| - | [[https://www.cnblogs.com/mrclr/p/8423136.html]] | + | [[https://www.cnblogs.com/Miracevin/p/9778266.html]] |
2020-2021/teams/no_morning_training/shaco/知识点/基础/前缀和.1590935043.txt.gz · 最后更改: 2020/05/31 22:24 由 admin
