寫在前面
本部分內(nèi)容借鑒于Young-children大佬對(duì)于差分?jǐn)?shù)組的講解，感謝大佬近弟。
定義
差分?jǐn)?shù)組類似于求解前綴和厉熟，給出原數(shù)組為d捌袜，差分?jǐn)?shù)組為f，那么有f[i] = d[i] - d[i - 1]，據(jù)此呵曹，可以發(fā)現(xiàn)兩條差分?jǐn)?shù)組的性質(zhì)：
-
d[i]等于f[i]的前綴和 -
d[i]的前綴和可以通過如下公式來求得：
用途
差分?jǐn)?shù)組主要支持兩種操作：1慰于、區(qū)間修改钮科；2、單點(diǎn)查詢
根據(jù)性質(zhì)一婆赠，可以得到若對(duì)某個(gè)區(qū)間[L, R] 增加一個(gè)數(shù) x绵脯，只需要使 f[L] += x; f[R + 1] -= x; 即可實(shí)現(xiàn)對(duì)區(qū)間的批量修改，而查詢時(shí)只需要求前綴和查詢單個(gè)元素休里，或者通過上述性質(zhì)二的公式查詢前綴和/區(qū)間和即可
備注
實(shí)際使用差分?jǐn)?shù)組時(shí)桨嫁，并不一定需要使用源數(shù)組構(gòu)造，可以直接根據(jù)區(qū)間修改來實(shí)現(xiàn)份帐，詳見1854. 人口最多的年份璃吧，同類型題號(hào)如下：370、731废境、732畜挨、995、1094噩凹、1109巴元、1526、1589驮宴、1674逮刨、1854，另外堵泽，使用差分?jǐn)?shù)組如果數(shù)據(jù)范圍較大修己，需要使用TreeMap代替數(shù)組實(shí)現(xiàn)，本質(zhì)大同小異
模板
由于差分?jǐn)?shù)組實(shí)際上就是一個(gè)數(shù)組迎罗，并不需要什么模板睬愤，所以這里粘貼一道題目及題解。題目轉(zhuǎn)自 acwing
題目
代碼
import java.util.*;
class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt() + 1, m = input.nextInt();
int[] nums = new int[n];
for(int i = 1; i < n; i++){
nums[i] = input.nextInt();
}
int[] f = new int[n + 1];
for(int i = 1; i < n; i++){
f[i] = nums[i] - nums[i - 1];
}
for(int i = 0; i < m; i++){
int l = input.nextInt(), r = input.nextInt(), c = input.nextInt();
f[l] += c;
f[r + 1] -= c;
}
for(int i = 1; i < n; i++){
f[i] += f[i - 1];
}
for(int i = 1; i < n; i++){
System.out.print(f[i] + " ");
}
}
}
