返回目录

前缀和

当你想频繁的求一个位置前面的数总和，但是 又害怕 $O(nm)$ 会超时,那你就可以把每一位的总和算出来，放在一个数组里，这个数组就叫前缀和数组

前缀和数组制作方法也很简单

for(int i=1;i<=n;i++){
    f[i]=f[i-1]+a[i]#这个f数组就是前缀和数组
}

差分数组

那么当你想要改一个区间的数字，但是又怕 $O(nm)$超时这话怎么这么熟悉你就可以把一个数减去前一个数的差给算出，然后放入一个数组中，这个数组就叫差分数组。

不过他不如前缀和数组这么好理解，你看一下下面