差分

---

差分是前缀和的逆运算。

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

例子：

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

题意：给定一串序列，可以进行无限次操作：对前任意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";
	}
}