YeziSnip

记录、沉淀、分享代码片段。

二维前缀和

构造二维前缀和数组，在 O(1) 时间复杂度内查询区间和。

const int N= 1e3+5;
using ll = long long;

ll a[N][N] = {0};
ll pref[N][N] = {0};

构造一维前缀和数组，在 O(1) 时间复杂度内查询区间和。

const int N = 1e5+5;
using ll = long long;

ll a[N] = {0};

for (int i = 1; i <= n; i++) {