差分

差分

差分是前缀和的逆运算。

       利用差分数组D [ ]可以把O ( n ) 的区间修改，变成O ( 1 ) 的端点修改，从而提高了修改操作的效率。
  但是，一次查询操作，即查询某个a [ i ] ，需要用D [ ]计算整个原数组a [ ]，计算量是O ( n ) 的，即一次查询的复杂度是O ( n )的。在上面的例题中，如果查询不是发生了一次，而是这样：有m次修改，有k次查询，且修改和查询的顺序是随机的。此时总复杂度是：m次修改复杂度O ( m )，k次查询复杂度O ( k n ) ，总复杂度O ( m + k n ) 。还不如直接用暴力法，总复杂度O ( m n + k )。
  这种题型是“区间修改 + 单点查询”，用差分数组往往不够用。因为差分数组对“区间修改”很高效，但是对“单点查询”并不高效。此时需要用树状数组和线段树来求解。
  树状数组常常结合差分数组来解决更复杂的问题，差分数组也常用于“树上差分”。