新芝士:二维前缀和

时间:2021-07-13 23:23:31

我真是太弱了,这么基础的算法这么晚了才会。。。。。。。(wo cai si le

首先我们来看一看: sum[i][j]=sum[i-1][j]+sum[i][j-1]+mp[i][j]-sum[i-1][j-1]; 这是她的初始化操作,可以通过容斥原理推一推,确实是这样的。
然后我们再来考虑一下她的查询:

inline int solve(int a,int b,int c,int d)
{
    return sum[a][b]+sum[c-1][d-1]-sum[a][d-1]-sum[c-1][b];
}

为什么呢?如果把式子写成这样就民白了: sum[a][b]-sum[a][d-1]-sum[c-1][b]+sum[c-1][d-1]。前边就是删掉了很大的两端,最后把多删掉的 加回去

例题:Luogu P2363 马农 (这道题正解是dp,但我暴力N^6直接cao过去了