无题

1.prefix 前缀和数组

p[i] = p[i-1] + a[i];

优点：便于数组查找

2.diff 差分数组

d[i] = a[i] - a[i-1];

优点：便于数组修改

3.二位前缀和

p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j];

4.二维差分

1.差分求法

d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]

以上这个求法，是将原式作为所求差分的前缀和。

2.标准求法

d[i][j] += a[i][j];

d[i + 1][j] -= a[i][j];

d[i][j + 1] -= a[i][j];

d[i + 1][j + 1] += a[i][j];

两种求法一样，可以互相推导

eg：d[i + 1][j] -= a[i][j]; = d[i][j] -= a[i-1][j]