2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和 [2020/05/24 12:01] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和 [2020/06/03 09:20] (当前版本) shaco |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 一些情况下，对数组的子区间和进行多次询问，遍历是一个费时的行为，前缀和在这里就很有用。 | 一些情况下，对数组的子区间和进行多次询问，遍历是一个费时的行为，前缀和在这里就很有用。 | ||
| - | ==== 多维前缀和 ==== | + | ===== 多维前缀和 ===== |
| {{:2020-2021:teams:no_morning_training:1.png?400|}}\\ | {{:2020-2021:teams:no_morning_training:1.png?400|}}\\ | ||
| 行 9: | 行 9: | ||
| 例如这张图，求绿色部分，就可以用整个减去横侧和纵侧的条，再加上被减两次的块。\\ | 例如这张图，求绿色部分，就可以用整个减去横侧和纵侧的条，再加上被减两次的块。\\ | ||
| 三维数组中同理，只是算式略不同。就是容斥定理的应用。\\ | 三维数组中同理，只是算式略不同。就是容斥定理的应用。\\ | ||
| - | 但是随着维度t变高，计算前缀和的容斥的复杂度是$2^t$，总复杂度达到了$O(n^t\times2^t)$。 | + | 但是随着维度t变高，计算前缀和的容斥的复杂度是 $2^t$ ，总复杂度达到了 $O(n^t\times2^t)$ 。 |
| 以三维为例： | 以三维为例： | ||
| 行 39: | 行 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$ 的矩阵，找一个最大的子矩阵，使得这个子矩阵里面的元素和最大。 |
| - | 最朴素的想法是枚举左下角、右上角并在内部枚举每个元素，复杂度O($n^6$)，利用前缀和降至O($n^4$)。\\ | + | 最朴素的想法是枚举左下角、右上角并在内部枚举每个元素，复杂度 $O(n^6)$ ，利用前缀和降至 $O(n^4)$ 。\\ |
| - | 好一点的想法是枚举上下边，中间的矩阵就成了一维数列，变成求最大区间和的问题，达到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|链接]] | |
| - | 这个题是付费题目所以....还是贴一下链接 [[https://ac.nowcoder.com/acm/contest/167/C?&headNav=acm|ouo]] | + | |
| <hidden 代码> | <hidden 代码> | ||
| 行 84: | 行 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/知识点/基础/前缀和.1590292888.txt.gz · 最后更改: 2020/05/24 12:01 由 shaco
