差分序列

前言

差分序列常用于维护需要进行区间加操作的序列，但是无法做到区间查询。

原理

已知一组序列，用数组 a 保存。a_i表示第序列第 i 个元素。建立一个数组b，其中：

                                                     b_i = a_i - a_i-1

因此 a₁ = b1 ，ai = bi + a_i-1

由于差分序列的性质，当我们对[l ,  r]这个区间统一进行加d操作时，只需要对

                                                b_l += d      b_r+1 –= d

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 100000
using namespace std;
int d[maxn + 5];
void add(int a, int b){
	d[a] += 1;
	d[b + 1] -= 1;
}
int main(){
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		add(a, b);
	}
	//依次输出元素 
	int t = d[1];
	printf("%d ", d[1]);
	for(int i = 2; i <= n; i++){
		printf("%d ", d[i] + t);
		t += d[i];
	}
	return 0;
}

与树状数组对比

	差分序列	树状数组
适合做	区间加 单点查询	单点加 区间查询
不适合做	区间查询	区间加