[随便写写]神奇的二维差分

二维差分,是相对于二维前缀和来的,它是一种可以支持(O(1))修改,单次求值(O(n))的一种特殊结构,它适用于需要多次修改,而求和次数很少的情况。

那么问题来了,给定二维数组(a[n][m]),它对应的二维差分数组怎么构造呢?类比一维数组差分的构造式(d[i]=a[i]-a[i-1]),我们可以类比得到二维差分的构造式:

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

这个构造式可能有点难理解,原理我也不知道该怎么形容(反正我直觉如此),然后验证一下这个式子也是对的(记住就好)。

然后接下来是修改操作,假设我们要修改区域(R:(i,j)sim(i',j'))(i'geqslant i,j'geqslant j),我们对差分数组进行如下的变换:

[d[i][j]+=v ]

[d[i'+1][j]-=v ]

[d[i][j'+1]-=v ]

[d[i'+1][j'+1]+=v ]

然后就视为对区域(R)进行了一次加值修改。

到查询的时候,就直接对整个差分数组求一遍二维前缀和就行了。

原文地址:https://www.cnblogs.com/loi-frank/p/13878391.html