前缀和与差分

前缀和与差分

JIeJaitt

2023 年 01 月 05 日

120 次浏览

暂无评论

553字数

算法竞赛

## 差分介绍

差分其实是前缀和的逆运算。给定$a[1],a[2],…a[n]$构造差分数组$b[N]$，使得$a[i]=b[1]+b[2]+…+b[i]$。

差分的核心操作：将$a[L~R]$全部加上$C$，等价于$b[L]+=c,b[R+1]-=C$。

1. 对于a[1~L-1]无影响
2. a[L~R]加上了C
3. a[R+1~N]无影响

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N=100010;

int n,m;
int a[N],b[N];

int insert(int l,int r,int c) {
    b[l]+=c;
    b[r+1]-=c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[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++) cout<<b[i]<<" ";
    
    return 0;
}
```

## **重新排序**

给定一个数组 $A$ 和一些查询 $L_i, R_i$，求数组中第 $L_i$ 至第 $R_i$ 个元素之和。这个问题很无聊，重新排列一下数组，使得最终每个查询结果的和尽可能地大。相比原数组，所有查询结果的总和最多可以增加多少?

输入第一行包含一个整数 $n$。第二行包含 $n$ 个整数 $A_1, A_2, · · · , A_n$，相邻两个整数之间用一个空格分隔。第三行包含一个整数 $m$ 表示查询的数目。接下来 $m$ 行，每行包含两个整数 $L_i、R_i$，相邻两个整数之间用一个空格分隔。输出一行包含一个整数表示答案。

对于 $30%$ 的评测用例，$n,m≤50$；对于 $50%$ 的评测用例，$n,m≤500$；对于 $70%$ 的评测用例，$n,m≤5000$；对于所有评测用例，$1≤n,m≤10^5，1≤A_i≤10^6，1≤L_i≤R_i≤n$。

输入样例：

```
5 
1 2 3 4 5 
2 
1 3 
2 5
```

输出样例：

```
4
```

原来的和为 $6+14=20$，重新排列为 $(1,4,5,2,3)$后和为 $10+14=24$，增加了 $4$。

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
int w[N],s[N];

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    
    scanf("%d",&m);
    while(m--) {
        int l,r;
        scanf("%d %d", &l, &r);
        
    }
}
```

## 资料

- [# 差分算法原理及代码模板](https://www.jianshu.com/p/444096786e49)
- [# 前缀和 & 差分](https://oi-wiki.org/basic/prefix-sum/)
- [797. 差分](https://www.acwing.com/problem/content/799/)
- - [AcWing 797. 差分题解](https://www.acwing.com/activity/content/code/content/39799/)
- [AcWing 4655. 重新排序【全程注释解析，能看懂就真的理解了！】  ](https://www.acwing.com/solution/content/159822/)
  - [AcWing 4655. 重新排序](https://www.acwing.com/activity/content/code/content/5115637/)
- https://www.acwing.com/activity/content/problem/content/832/

最后修改：2023 年 12 月 14 日