美文网首页
差分数组

差分数组

作者: 华雨欣 | 来源:发表于2020-11-29 20:27 被阅读0次

    写在前面

    本部分内容借鉴于Young-children大佬对于差分数组的讲解,感谢大佬。

    定义

    差分数组类似于求解前缀和,给出原数组为d,差分数组为f,那么有f[i] = d[i] - d[i - 1],据此,可以发现两条差分数组的性质:

    • d[i]等于f[i]的前缀和
    • d[i]的前缀和可以通过如下公式来求得:

    用途

    差分数组主要支持两种操作:1、区间修改;2、单点查询
    根据性质一,可以得到若对某个区间[L, R] 增加一个数 x,只需要使 f[L] += x; f[R + 1] -= x; 即可实现对区间的批量修改,而查询时只需要求前缀和查询单个元素,或者通过上述性质二的公式查询前缀和/区间和即可

    备注

    实际使用差分数组时,并不一定需要使用源数组构造,可以直接根据区间修改来实现,详见1854. 人口最多的年份,同类型题号如下:370、731、732、995、1094、1109、1526、1589、1674、1854,另外,使用差分数组如果数据范围较大,需要使用TreeMap代替数组实现,本质大同小异

    模板

    由于差分数组实际上就是一个数组,并不需要什么模板,所以这里粘贴一道题目及题解。题目转自 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] + " ");
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:差分数组

          本文链接:https://www.haomeiwen.com/subject/yunkwktx.html