差分数组_差分数组的概念和用法

差分数组_差分数组的概念和用法介绍: 区间修改查询问题一般会想到用线段树或者树状数组来做,但是题目是离线查询,即完成修改后再查询的话,可以用到差分数组。 差分数组: 对于数组a[i],我们令d[i]=a[i]-a[i-1] (特殊的,第一个为d[1]=a[1]),则d[i]为一个差分数组。 我们发现统计d数组的前缀和sum数组,

差分数组_差分数组的概念和用法"

介绍:

区间修改查询问题一般会想到用线段树或者树状数组来做,但是题目是离线查询,即完成修改后再查询的话,可以用到差分数组

差分数组:

对于数组a[i],我们令d[i]=a[i]-a[i-1]  (特殊的,第一个为d[1]=a[1]),则d[i]为一个差分数组。
我们发现统计d数组的前缀和sum数组,有
sum[i]=d[1]+d[2]+d[3]+…+d[i]=a[1]+a[2]-a[1]+a[3]-a[2]+…+a[i]-a[i-1]=a[i],即前缀和sum[i]=a[i];
因此每次在区间[l,r]增减x只需要令d[l]+x,d[r+1]-x,就可以保证[l,r]增加了x,而对[1,l-1]和[r+1,n]无影响。 复杂度则是O(n)的。
 
 

题目:

HDU 1556 Color the ball

题意:

给出一个区间n, n个数初始值都是0, 给出n个区间修改,修改是在[l,r]上加1, 最后输出n个数。

分析:

属于离线查询, 可以维护差分数组来求出最后的数字。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define INF 0x3f3f3f3f
 4 const int N = 100000 + 10;
 5 int m, q;
 6 long long a[N], d[N], sum[N];
 7 int main() {
 8     int n;
 9     while (scanf("%d", &n) && n) {
10         memset(a, 0, sizeof(a));//初始化都为0
11         int l, r;
12         memset(d, 0, sizeof(d));
13         d[1] = a[1];//特殊处理第一个数
14         for (int i = 0; i < n; i++) {
15             scanf("%d%d", &l, &r);
16             d[l] += 1;
17             d[r+1] -= 1;
18         }
19         memset(sum, 0, sizeof(sum));
20         for (int i = 1; i <= n; ++i) {
21             sum[i] = sum[i-1] + d[i]; //求d[i]前缀和, 也就是修改后的a[i]
22         }
23         for (int i = 1; i <= n; ++i){
24             printf("%lld",sum[i]);
25             if(i != n) printf(" ");
26         }
27         puts("");
28     }
29 
30     return 0;
31 }

BZOJ 3043 IncDec Sequence

题意:

给定一个长度为n的数列a[i],每次可以选择一个区间[l,r],使这个区间内的数都加一或者都减一。

求:(1)至少需要多少次操作才能使数列中的所有数都一样。

  (2)在保证最少次数的前提下,最终得到的数列有多少种

分析:

因为我们最终是求一个所有数的一样的序列, 所以其差分数组就是除了d[1]外,d[2]~d[n]全为0。

然后题目中区间加一或者区间减一操作, 其实就是在差分数组中, 找出两个下标i, j, d[i]++, d[j]–(或者d[i]–, d[j]++)

所以我们就可以利用这个操作把d[2]~d[n]中的正数和负数中和, 然后还有会一部分正数(或负数)多出来, 我们只需要在这个点上面直接加减就好(这个单点操作其实有两重意义,涉及第二问)

我们求出d[2]~d[n]的正数和绝对值pos, 负数和绝对值neg

所以第一问的答案就是max(pos,neg)

刚刚提到了有一个单点操作的意义, 我们就拿d[i]++来说吧

第一种含义是, 因为d[1]是什么并没有关系, 所以可以代表d[1]– , d[i]++, 实际意义就是数组a[1]~a[i-1]都减去1。

第二种含义是, 因为修改区间[l,r]加一是在d[l]++, d[r+1]–, 如果这个r等于n的时候, 那么r+1并没有意义, 所以也成了单点操作, 实际意义就是a[i]~a[n]加上1。

就是说那个多出来的d[i]可以配给d[1]或者d[n+1](没有意义)

所以我们的问题二可以转化为d[1]的取值个数, 那么可以配0次, 1次…到abs(pos-neg)次, 所以最终d[1]的取值总共abs(pos-neg) + 1次。

 

今天的文章差分数组_差分数组的概念和用法分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/49510.html

(0)
编程小号编程小号
上一篇 2023-09-03 07:06
下一篇 2023-09-03 07:17

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注