一维差分算法

目录

背景：

一维插分应用场景

一维差分法

原理解释

背景：

在刷javaA组蓝桥本真题时，碰到了一个用二维差分方法的解题思路，意识到自己差分不熟悉，就想先学习一下一维差分。

一维插分应用场景

题目给出一个一维数组，并多次修改某一区间的值。

例如：一个数组长度为8 ，初始均为0，

输入数据：   m 表示有m个修改区间

接下来m行   每行3个值left right value  表示区间的左右边界，以及该区间的每个元素加上value

输出：返回修改后的数组

例： 输入：        3

                            1        7        1

                             2        4        -3

                              4        5        4

输出：[ 1,-2,-2,2,5,1,1,0 ]

不用一维差分的解题方法。

import  java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int [] arr = new int[8];
        int m = sc.nextInt();
        for (int i=0;i<m;i++){
            int left = sc.nextInt();
            int right =sc.nextInt();
            int value = sc.nextInt();
            for (int j=left;j<=right;j++){
                arr[j-1] +=value;
            }
        }
        for (int num : arr){
            System.out.print(num+" ");
        }
    }
}
/*

输入：
3
1 7 1
2 4 -3
4 5 4
*/

//输出 1 -2 -2 2 5 1 1 0

传统算法的时间复杂度：

假设：数组的大小为n，修改次数为m，修改区间平均下来是 1/2 n

那花费时间为 1/2mn 即时间复杂度为O(mn)

一维差分法

先说一下时间复杂度

一维差分的时间复杂度为O(n+m)

import  java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int [] arr = new int[8];
        int m = sc.nextInt();
        for (int i=0;i<m;i++){
            int left = sc.nextInt();
            int right =sc.nextInt();
            int value = sc.nextInt();
            arr[left-1]+=value;
            arr[right]-=value;

        }
      for (int i=1;i<arr.length;i++){
          arr[i]+=arr[i-1];
      }
      for (int num :arr){
          System.out.print(num+" ");
      }
    }
}
/*

输入
3
1 7 1
2 4 -3
4 5 4
*/
//输出 1 -2 -2 2 5 1 1 0

原理解释

   每次要对区间[left, right]内的元素进行增减操作时，我们只需在差分数组中对两个位置进行修改：

• arr[left]增加某个值val；
• arr[right+1]减少相同的值val。

比如第一次要对区间[0,6]即第1到第7个元素修改，数值加1

那么只需让

arr[0]=1;

arr[7]=-1;

那么数组arr为 【1，0，0，0，0，0，-1，0】  状态1

实际数组应该是【1，1，1，1，1，1，1，0】  状态2

如何从状态1转化成状态2？

只需让状态1的数组从第二个元素开始加上前一位一维

比如说arr1=【1，0，0，0，0，0，-1，0】

那么遍历arr1  arr[i]=arr[i-1]+arr[i]

就可得到状态2的数组arr2=【1，1，1，1，1，1，1，0】

所以经历三次区间标记后

arr=【1，-3，0，4，3，-4，0，-1】

for (int i=1;i<arr.length;i++){
          arr[i]+=arr[i-1];
      }

经过遍历之后arr就变成【1，-2，-2，2，5，1，1，0】