2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和 [2020/06/02 21:59] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和 [2020/06/03 09:20] (当前版本) shaco |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | **格式**： | ||
| - | |||
| - | - 第二层标题建议改为二级标题（5个 ''=''） | ||
| - | - 行间公式建议使用 ''$$ $$'' 包裹，而不是 ''\[\]'' | ||
| - | - 三维前缀和的三个公式建议分三行较为美观 | ||
| - | |||
| - | **内容**：<del>例题中涉及到了不定维数的前缀和，可否拿出来单独讲一下？</del>嗯还是不用讲了。。 | ||
| - | |||
| ====== 前缀和 ====== | ====== 前缀和 ====== | ||
| 行 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)$。维数较高的情况下会节省一些时间。 | ||
| 行 63: | 行 57: | ||
| 例如 $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|链接]] | ||
| 行 97: | 行 92: | ||
| ===== 参考 ===== | ===== 参考 ===== | ||
| [[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/知识点/基础/前缀和.1591106375.txt.gz · 最后更改: 2020/06/02 21:59 由 shaco
