尺取、差分与前缀和整理

常规
1

尺取、差分与前缀和

1 前缀和
一维前缀和
构建

for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		s[i] = s[i - 1] + a[i];
	}

输出区间和
cout << s[r] - s[l - 1]
（l是左，r是右）
二维前缀和
构建

for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			scanf("%d", &a[i][j]);
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	}

输出子矩阵和

int x, y, x2, y2;
scanf("%d%d%d%d", &x, &y, &x2, &y2);
	printf("%d\n", s[x2][y2] - s[x - 1][y2] - s[x2][y - 1] + s[x - 1][y - 1]);

（x, y是左上，x2, y2是右下）

2 差分
一维差分
构建

for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		d[i] += a[i];
		d[i + 1] -= a[i];
	}

增加操作

int l, r, h;
scanf("%d%d%d", &l, &r, &h);
d[l] += h;
d[r + 1] -= h;

（h为增加的值）

输出原数组

for(int i = 1; i <= n; i++)
{
	a[i] = a[i - 1] + d[i];
	printf("%d ", a[i]);
}

（前缀和）

二维差分
构建

for(int i = 1; i <= n; i++)
{
	for(int j = 1; j <= m; j++)
	{
		scanf("%d", &a[i][j]);
		int p = a[i][j];
		d[i][j] += p;
		d[i + 1][j] -= p;
		d[i][j + 1] -= p;
		d[i + 1][j + 1] += p;
	}
}

增加操作

int x, y, x2, y2, h;
scanf("%d%d%d%d%d", &x, &y, &x2, &y2, &h);
d[x][y] += h;
d[x2 + 1][y] -= h;
d[x][y2 + 1] -= h;
	d[x2 + 1][y2 + 1] += h;

输出原数组

for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
			printf("%d ", d[i][j]);
		}
		printf("\n");
	}

（二维前缀和）

3 双指针/尺取
 双指针是一种优化时间复杂度的算法（例如二分算法）

 eg1:
简单的求和(ID: 9736)

#include <bits/stdc++.h>
using namespace std;

long long a[100005];

bool cmp(int x, int y)
{
	return x < y;
}

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
	}
	sort(a + 1, a + n + 1, cmp);
	long long l = 1, r = n, cnt = 0;
	while (r >= l)
	{
		if (a[l] + a[r] < k)
		{
			l++;
		}
		else if (a[l] + a[r] > k)
		{
			r--;
		}
		else
		{
			long long t1 = a[l], t2 = a[r], p1 = 0, p2 = 0;
			while (a[l] == t1 && r >= l && l <= n)
			{
				l++;
				p1++;
			}
			while (a[r] == t2 && r >= l && r >= 1)
			{
				r--;
				p2++;
			}
			cnt += p1 * p2;
		}
	}
	printf("%lld\n", cnt);
	return 0;
}

连续子区间的和(ID: 15648)

#include <bits/stdc++.h>
using namespace std;

int a[100005], s[100005];

int main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	int l = 1, r = 0, sum = 0, cnt = 0;
	while (!(r > n && sum < m))
	{
		sum = s[r] - s[l - 1];
		if (sum < m)
		{
			r++;
		}
		if (sum > m)
		{
			l++;
		}
		if (sum == m)
		{
			cnt++;
			l++;
		}
	}
	cout << cnt;
	return 0;
}
6 个赞