差分 - wenzhoullq/leetcode GitHub Wiki
一维差分
diff长度是原长度+1,下标是跟arr[]对应的 差分是单点修改,区间变化
模板
int[] diff=new int[len+1];
for(int[] query:queris){
diff[q[0]]++;
diff[q[1]+1]--;
}
for(int i = 0; i < len; i++) diff[i]+=diff[i-1];
}
题目
1871. 跳跃游戏 VII 边更新边刷表
1094. 拼车 //上下车上,对于差分的起始位置需要考虑
1589. 所有排列中的最大和 根据访问的次数决定排序的次数
二维差分
int[][] ans = new int[n][n],f = new int[n+1][n+1];
for(int[] query:queries){
int r1 = query[0],c1 = query[1],r2 = query[2],c2 = query[3];
f[r1][c1]+=add;
f[r1][c2+1]-=add;
f[r2+1][c1]-=add;
f[r2+1][c2+1]+=add;
}
for (int i = 1; i < n; i++) for (int j = 0; j < n; j++) ans[i][j] += ans[i - 1][j];
for (int i = 0; i < n; i++) for (int j = 1; j < n; j++) ans[i][j] += ans[i][j - 1];
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) ans[i][j] = f[i][j];