差分序列
发布时间：2020-12-14 04:46:51 所属栏目：大数据 来源：网络整理
导读：前言 差分序列常用于维护需要进行区间加操作的序列，但是无法做到区间查询。 原理 已知一组序列，用数组 a 保存。a i 表示第序列第 i 个元素。建立一个数组b，其中： ???????????????????????????????????????????????????? b i = a i - a i-1 因此 a 1 = b1
前言差分序列常用于维护需要进行区间加操作的序列，但是无法做到区间查询。原理已知一组序列，用数组 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; } 与树状数组对比
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |