差分数组：PIPI的区间操作Ⅰ

以你之姓@ 2023-10-06 22:03 11阅读 0赞

## 差分数组：PIPI的区间操作Ⅰ ##

#### 文章目录 ####

*  差分数组：PIPI的区间操作Ⅰ
 *   *   *  差分数组
         *  问题：
         *  思路：
         *  代码：

#### 差分数组 ####

差分数组其实就是对数组做差分，即前一项减去后一项，差分数组的定义为：对于有n个元素的数组a，差分数组b为数组a中每一项与前一项的差值。显然，b\[1\]=a\[1\]-0=a\[1\]；对于整数i∈\[2,n\]，则有b\[i\]=a\[i\]-a\[i-1\]。例子如下：  
![在这里插入图片描述][a07e589923f44affabbac73ecc4f7ae4.png]  
  我们不难发现，设sum数组为b数组的前缀和数组，那么sum数组的值和a数组的值是对应相等的，也就是说，相对于数组a的差分数组b来说，a数组就是其前缀和数组。这是差分数组的重要性质，差分数组的前缀和对应原数组，也就是我们可以将差分数组通过前缀和还原为原数组  
![在这里插入图片描述][8b833eb91d3d46fb84897500fa899879.png]  
  那么差分数组有什么作用呢？答案是快速处理区间加减操作。例如对区间\[L,R\]中的每个数加上x，我们通过差分数组的性质知道，第一个受影响的差分数组中的元素为b\[L\]，因为a\[L\]加上了x，a\[L - 1\]没有加，所以令b\[L\]+=x；最后一个受影响的差分数组中的元素为b\[R+1\]，因为a\[R\]加上了x，a\[R + 1\]没有加，所以令b\[R+1\]-=x。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]

这样对于区间加减操作，我们不必对区间内每一个数进行处理，只需处理两个差分后的数即可。例如，我们要对a数组\[2,3\]区间的每个数加上3，再对a数组\[3,4\]区间的每个数加上1，求最终a数组的每个数是多少：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

差分数组特别适合解决多次区间加减操作，最后再询问的问题。例如，若需要对区间进行n次加减，最后求区间和，用for循环的时间复杂度为O(n ^ 2)，而使用差分数组的时间复杂度为O(n)。

#### 问题： ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 思路： ####

差分数组板子题。我们对原数组a求差分数组b，那么对每个区间加操作，我们就令b\[L\]+=P并令b\[R+1\]-=P。如果是区间减操作，就令b\[L\]+=-P并令b\[R+1\]-=-P就行了。进行完m次操作后，我们对b数组求其前缀和数组，即可把它还原成经过m次操作后的a数组。然后再对a数组求前缀和sum数组，那么对接下来的q次询问，我们对每个问题输出sum\[r\]-sum\[l-1\]即可。

#### 代码： ####

import java.util.*;
    
    public class Main {
        
    
        static long[] subArray = new long[100005];
        static long[] array = new long[100005];
        static long[] preSum = new long[100005];
        public static void main(String[] args) {
        
            int n, m, q, op, l, r, i;
            long p;
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            m = scanner.nextInt();
            q = scanner.nextInt();
            for (i = 0; i < n; i++) {
        
                array[i] = scanner.nextLong();
            }
            subArray[0] = array[0];
            for (i = 1; i < n; i++) {
        
                subArray[i] = array[i] - array[i - 1];
            }
            for (i = 0; i < m; i++) {
        
                op = scanner.nextInt();
                l = scanner.nextInt() - 1;
                r = scanner.nextInt() - 1;
                p = scanner.nextLong();
                if (op == 1) {
        
                    subArray[l] += p;
                    if (r + 1 < n) {
        
                        subArray[r + 1] -= p;
                    }
                } else {
        
                    subArray[l] -= p;
                    if (r + 1 < n) {
        
                        subArray[r + 1] += p;
                    }
                }
            }
            array[0] = subArray[0];
            for (i = 1; i < n; i++) {
        
                array[i] = array[i - 1] + subArray[i];
            }
            preSum[0] = array[0];
            for (i = 1; i < n; i++) {
        
                preSum[i] = preSum[i - 1] + array[i];
            }
            for (i = 0; i < q; i++) {
        
                l = scanner.nextInt() - 1;
                r = scanner.nextInt() - 1;
                System.out.println(l == 0 ? preSum[r] : preSum[r] - preSum[l - 1]);
            }
        }
    }

[a07e589923f44affabbac73ecc4f7ae4.png]: https://img-blog.csdnimg.cn/a07e589923f44affabbac73ecc4f7ae4.png
[8b833eb91d3d46fb84897500fa899879.png]: https://img-blog.csdnimg.cn/8b833eb91d3d46fb84897500fa899879.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/73a347e1b2f6426ab8edaf2c560bd454.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/5edb3df47f474224bd55df502bb296c1.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/0f24bb3a064d4f0483bd7a4520ef5c60.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/b1439fde340f42e99459e3d4b48c85e2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16