题目描述
输入一个长度为n的整数序列。
接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数,表示整数序列。
接下来m行,每行包含三个整数l,r,c,表示一个操作。
输出格式
共一行,包含n个整数,表示最终序列。
数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例:
3 4 5 3 4 2
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
差分
已知前缀和 a[n], 构造差分数组b[n]
满足条件: a[i] = b[1] + b[2] + … + b[i], 即ai是b1,b2,..bi的前缀和
差分就是前缀和的逆运算
构造 b[n], 通过插入操作构造 b[n]
b[1] = a[1]
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
...
b[n] = a[n] - a[n-1]
b[n]称为a[n]的差分
a[1] = b[1]
a[2] = b[2] + b[1]
= a[2] - a[1] + a[1]
= a[2]
a[3] = b[3] + b[2] + b[1]
= a[3] - a[2] + a[2] - a[1] + a[1]
= a[3]
...
a[n] = b[n] + b[n - 1] + ...b[2] + b[1]
= a[n] - a[n-1] + a[n-1] - a[n - 2] +... + a[2] - a[1] + a[1]
= a[n]
a[n]称为b[n]的前缀和
差分的用途
对a数组的某个区间[1, r]内的数全部加上c, 现在只需要对b数组的l位置加上c, r + 1位置减去c
构造a[1...4]的数组
b[1] = a[1]
b[2] = a[2] - a[1]
b[3] = a[3] - a[2]
b[4] = a[4] - a[3]
b[5] = a[5] - a[4]
假设在数组a中[1, 4]位置 + c
原来a数组中 a[1] a[2] a[3] a[4] a[5] 4个位置都加上+c
使得 a[1]+c a[2]+c a[3]+c a[4]+c a[5]
现在b数组中 b[l]+c b[2] b[3] b[4] b[(r=4)+1]-c
利用b数组重新计算a的前缀和
a[1] = b[l] + c
= a[1] + c
a[2] = b[2] + b[1] + c = a2 - a1 + a1 + c
= a2 + c
a[3] = b[3] + b[2] + b[1] + c = a3 - a2 + a2 - a1 + a1 + c
= a3 + c
a[4] = b[4] + b[3] + b[2] + b[1] + c = a4 - a3 + a3 - a2 + a2 - a1 + a1 + c
= a4 + c
a[5] = b[5] - c + b[4] + b[3] + b[2] + b[1] + c
= -c + a5- a4 + a4 - a3 + a3 - a2 + a2 - a1 + a1 + c
= a5
至此,这和我们预期的一致,实现了对区间[1,4]加C操作
这使得我们对区间操作的时间复杂度从O(n)变成了O(1)
实现思路
1.初始化,设置全为0的前缀和a数组,全为0的差分数组b
2.构造a数组,为了获得原始的a数组,在a的区间[i, i]插入一个数,则需要在b数组中i位置+a[i], i+1位置上-a[i]
至此a, b的数组填充结束
3.通过输入的l, r, c, 用公式b[l] += c, b[r+1] -= c实现a区间[l, r]全部插入c的操作
```
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
//构造b数组
for(int i = 1; i <= n; i ++) insert(i, i, a[i]);
//插入操作
while(m --){
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}
//利用数组b计算a的前缀和
for(int i = 1; i <= n; i ++) b[i] += b[i - 1];
for(int i = 1; i <= n; i ++) printf("%d ", b[i]);
return 0;
```
java
import java.util.Scanner;
public class Main{
static int n, m;
static int N = 100010;
static int[] a = new int[N], b = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 1; i <= n; i ++) a[i] = sc.nextInt();
for(int i = 1; i <= n; i ++) insert(i, i, a[i]);
while(m -- != 0){
int l, r, c;
l = sc.nextInt();
r = sc.nextInt();
c = sc.nextInt();
insert(l, r, c);
}
for(int i = 1; i <= n; i ++) b[i] += b[i - 1];
for(int i = 1; i <= n; i ++) System.out.print(b[i] + " ");
}
public static void insert(int l, int r, int c){
b[l] += c;
b[r + 1] -= c;
}
}
python
a = [0] * 100010
b = [0] * 100010
def insert(l, r, c):
b[l] += c
b[r + 1] -= c
def main():
n, m = list(map(int, input().split()))
global a
global b
a = list(map(int, input().split()))
for i in range(n):
insert(i + 1, i + 1, a[i])
while(m != 0):
l, r, c = list(map(int, input().split()))
insert(l, r, c)
m -= 1
for i in range(n):
b[i + 1] += b[i]
for i in range(n):
print(b[i + 1], end=' ')
main()
样例
#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c){
b[l] += c;
b[r + 1] -= c;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
/*
初始的时候,假设
a数组 全为0. 则差分数组必然为0
当向a数组中插入一个值,需要计算其区间[i, i]的差分值,利用差分性质,将当前的值插入到差分数组中。
*/
for(int i = 1; i <= n; i ++) insert(i, i, a[i]);
while(m --){
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}
for(int i = 1; i <= n; i ++) b[i] += b[i - 1];
for(int i = 1; i <= n; i ++) printf("%d ", b[i]);
return 0;
}