https://wiki.cvbbacm.com/ 2026-04-29T23:36:26+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-06-03T09:20:16+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E5%9F%BA%E7%A1%80:%E5%89%8D%E7%BC%80%E5%92%8C&rev=1591147216&do=diff 前缀和 一些情况下，对数组的子区间和进行多次询问，遍历是一个费时的行为，前缀和在这里就很有用。 多维前缀和 在一个二维数组中要求一个方形区域的和。这里同样可以运用前缀和。$2^t$$O(n^t\times2^t)$$$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]}$$$O(n^t\times t)$$n\times n$$O(n^6)$$O(n^4)$$O(n^3)$$i(0\le i<n)$$n\le2^{20}$$n=2^{10}$ text/html 2020-06-02T21:58:26+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E5%9F%BA%E7%A1%80:%E5%B0%BA%E5%8F%96%E6%B3%95&rev=1591106306&do=diff 尺取法 two pointers 简介&思想 通常是具有单调特征序列、寻找连续子区间接近目标值的问题中应用。 关注左右两端的指针，当选定的区间中所关注的值大于目标值时将左侧指针右移，当选定的区间中所关注的值小于目标值时将右指针右移，直至终点。枚举区间的复杂度为O(n)，计算区间的值的复杂度通常是O(1)，不排除有例外。$O(n^2)$$O(n)$$a[i]$