前缀和
一维前缀和
- 2430. 对字母串可执行的最大删除数
- 通过记录字符串前缀哈希值，及对应的底数幂次 -> 快速计算任意一个连续子字符串的哈希值
二维前缀和
-
- cpp前缀和模拟
- 计算公式
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]
利用动规预处理数据，为后续计算做准
- 这题考虑遍历（j, k） -> 这里就么有想到
- 创建二维数组mem -> 使用二维数组记录大小元素个数信息也没有想到
- 有部分前缀和的思想在里面
- 事先计算
[x, y]范围里，比y小的元素数目 -> 记录到mem[x][y] - 计算
[y, z]范围里，比y大的元素数目 -> 记录到mem[x][z]