首页 > 其他 > 详细

差分序列

时间:2019-05-18 23:48:40      阅读:53      评论:0      收藏:0      [点我收藏+]

标签:但是   树状   保存   spa   names   ret   输出   我们   add   

前言

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

原理

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

                                                     bi = ai - ai-1

因此 a1 = b1 ,ai = bi + ai-1

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

                                                bl += d      br+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;
}

与树状数组对比

 

差分序列

树状数组

适合做

区间加

单点查询

单点加

区间查询

不适合做

区间查询

区间加

差分序列

标签:但是   树状   保存   spa   names   ret   输出   我们   add   

原文:https://www.cnblogs.com/woxiaosade/p/10887473.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号