为了统一处理,我们通常让前缀和数组从1开始,把前缀数组s[0]定成0。
这样求[1,x]可以表示为s[x]-s[0],从而可以用相减的方式统一处理所有的情况
故而我们也要考虑边界问题,特别在二维差分/前缀和的时候
模板代码:
//我们定义原数组(前缀和)为A,差分数组为B
//一维差分数组插入核心,初始化差分数组 insert[i,i,A[i]]
public static void insert(int l,int r,int v){
B[l]+=v;
B[r+1]-=v;
}
//二维插入差分数组插入核心,初始化差分数组 insert[i,j,i,j,A[i][j]]
public static void insert(int x1,int y1,int x2,int y2,int v){
B[x1][y1]+=v;
B[x1][y2+1]-=v;
B[x2+1][y1]-=v;
B[x2+1][y2+1]+=v;
}