差分¶

差分实质探究¶

差分的实质：区间加同一个数可以差分是因为增量序列的递推式为 a_i=a_{i−1}，而后一个数减去前一个数正好抵消。

如果我们要在左上角是 (x1,y1)，右下角是 (x2,y2) 的矩形区间每个值都 +c，代码如下

diff[x1][y1] += c;
diff[x1][y2+1] -=c;
diff[x2+1][y1] -=c;
diff[x2+1][y2+1] += c;

二维差分的复原

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        q[i][j]+=q[i-1][j]+q[i][j-1]-q[i-1][j-1];
    }
}

一个很愚蠢的错误

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        a[i][j]=q[i][j]+q[i-1][j]+q[i][j-1]-q[i-1][j-1];
    }
}

对于一颗差分树，我们在节点u加上val，那么就相当于我们把u到根节点路径上的每一个点都加上了val。那么加上v是这条路径中的一个点，那么我们在v上-val就相当于把路径u-v加上了val。

画图很好理解。我们要清楚树上前缀和是怎么样的就容易理解了。

所以对于在树上把路径u-v都加上val的差分方法就是 \(tr_u+val,tr_v+val,tr_{lca(u,v)}-val,tr_{fa[lca(u,v)]}-2\times val\)