1. 前缀和数组

假设我们需要求指定数组中 l ~ r 范围元素的和

方法一:我们使用一个二维数组存储所有l-r的元素和的结果 (需要n*n/2的空间)

方法二:使用前缀和数组 求出 每个元素 0~元素本身的和(需要n的空间存储结果)

当我们求 3 ~ 7 范围的和 我们返回 ans[7]即0~7的结果 减去 ans[2]即0~2的结果 即可以快速取得指定范围内的合

sum[i···j] = arr[0···j] - arr[0···i-1]

此方法我们称为 前缀和数组