C/C++语言100题练习计划 77——区间问题（差分实现）

名人说：故立志者，为学之心也；为学者，立志之事也。—— 王阳明
进度：C/C++语言100题练习计划专栏，目前77/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description
现在有一个长度为n的序列，淘气的小明对这个序列进行了多次的修改，每次修改的方式都是，对该序列的一段区间整体加上一个数。多次修改之后，小明想知道该序列中的某一些位置的值是多少，聪明的你一定能帮帮他。

2.输入输出

Input

第一行为一个正整数n表示该序列的长度

第二行为n个正整数，表示该序列

第三行为一个正整数q表示接下来有q次修改

接下来q行每行3个整数a b v，其中a, b表示修改的区间[a,b]，v表示对该区间中的每个数增加的值。

接下来一行为一个整数p表示接下来有p次询问。

接下来p行每行1个整数 c 表示小明想知道序列中第c位置的值是多少。

Output

输出共p行，每行对应输入的询问，输出经过修改后该位置的值。

3.测试样例

Sample Input

5
4 3 2 5 1
3
1 3 4
2 4 -1
3 5 2
2
3
2

Sample Output

7
6

★提示：
对于100%的数据n < 10000, q < 10000, 0 < a <= b <= n, |v| < 100, p < 10000

二、源码实现

#include
#include
using namespace std;
//对修改的部分进行差分，每次操作只用两次操作，降低了一维的时间复杂度。
//根据提示的范围，定义的数组大小稍大一些，如下
//序列数组
int line[10010];
//差分数组 修改的部分的差分
int change[10010];
//定义 n 表示该序列的长度 q 表示接下来有q次修改 p 表示有p次询问
int n, q, p;

int main()
{
	//输入序列的长度
	scanf("%d", &n);
	//根据序列的长度大小，输入该序列
	for(int i=1; i<=n; ++i)
		scanf("%d", &line[i]);
	//输入修改的次数
	scanf("%d", &q);
	//循环输入q次修改(借助差分进行修改)
	for(int i=1; i<=q; ++i)
	{
		int a, b, val;
		scanf("%d %d %d", &a, &b, &val);
		change[a]+=val;
      	change[b+1]-=val;
      //利用差分修改change数组
	}
    for(int i=1;i<=n;i++)
    {
      change[i]+=change[i-1];//将差分数组抹平
    }
  	//输入询问的次数
	scanf("%d", &p);
	//询问p次，输出经过修改后该位置的值
	for(int i=1;i<=p;++i)
	{
		int temp;
		scanf("%d", &temp);
		printf("%d\n",line[temp]+change[temp] );
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

★关于差分：
1️⃣差分法：让一个数字序列的某一特定范围内的所有值都加上或减去一个常数；
所谓差分，就是让序列中的每一个元素与前一个元素作差，将序列中某区间的变化分裂成每个元素变化，省去每次都遍历整个序列的麻烦，这样就提高了算法执行的效率等。
2️⃣差分函数如下：
void insert( int l , int r , int c )
{
          s[l] += c;
          s[ r + 1] -= c;
}

三、测试结果

5
4 3 2 5 1
3
1 3 4
2 4 -1
3 5 2
2
3
7
2
6

--------------------------------
Process exited after 1.509 seconds with return value 0
请按任意键继续. . .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ღ( ´･ᴗ･` )比心