寫在前面

本部分內(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] + " ");
        }
    }
}