# 差分

***

差分是前缀和的逆运算。

差分数列，由该位置元素和前一个元素的差构成。

> 例子：
>
> 2 3 5 7 11 13 17 19
>
> 差分数列：2 1 2 2 4 2 4 2

### 作用：

用于将区间操作转换成单点操作，原本对区间的操作在差分数列上体现的是对1-2个单点的操作。

例如，对数列的前k项同时-1，差分数列上表现为对第1项减1，对第n+1项加1，其余项不变。

### 例题：

[Problem - D - Codeforces](https://codeforces.com/contest/1443/problem/D)

题意：给定一串序列，可以进行无限次操作：对前任意k个数减1或对后任意k个数减1，求是否能将这个数组的元素全部置0.

发现是前k个和后k个的区间问题，考虑维护差分，把原数列置零等同于把差分数列置零（第一项是0，剩下的项和第一项的差都是0）。

对差分数列来说，对前k个数减1只意味着对第1项减1，对第n+1项加1，其余项不变；对后k个数减1对差分数列只意味着对第k项减1。

容易发现，我们可以对任意正数做任意次减1，直到减到0为止；唯一的变数在于负数，某负数要加到0，只能靠减第一项来实现。所以只用判断第一项减到0时负数能不能都加到0就行了。

代码：

```
const int maxn = 30005;
int a[maxn],dif[maxn];
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		dif[1] = a[1];
		int tot = 0;
		for (int i = 2; i <= n; i++) {
			dif[i] = a[i] - a[i - 1];
			if (dif[i] < 0) tot-=dif[i];
		}
		if (a[1] >= tot) cout << "YES\n";
		else cout << "NO\n";
	}
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/cha-fen.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.