能够在$O(1)$时间内求出区间和。

一维前缀和

a[1], a[2], a[3], ..., a[n]

s[i] = a[1] + a[2] + ... + a[i]

a[i] + a[i+1] + ... + a[j] = s[j] - s[i]

二维前缀和