计算数列和的时候 比方说有一个数列 我们要求算任意两项之间的所有项的和
| 列标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 值 | a | b | c | d | e | f |
| 如果要算2～4 那就是c+d+e | ||||||
| 看起来还行 | ||||||
| 但是如果是要算每一种可能的数列和 | ||||||
| 拿总共就要算很多很多次 | ||||||
| 复杂度非常的高 | ||||||
| 于是乎我们就想到了一个叫前缀和的办法 |
如果用普通方法计算
计算数列和的时候 比方说有一个数列 我们要求算任意两项之间的所有项的和
| 列标 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 值 | a | b | c | d | e | f |
| 如果要算2～4 那就是c+d+e | ||||||
| 看起来还行 | ||||||
| 但是如果是要算每一种可能的数列和 | ||||||
| 拿总共就要算很多很多次 | ||||||
| 复杂度非常的高 | ||||||
| 于是乎我们就想到了一个叫前缀和的办法 |
如果用普通方法计算