devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

最全线段树例题

作者：我家自动化 | 2024-03-02 11:11:52

赞

踩

线段树例题

例题1： 给一个长度n的序列, 对于每个询问 询问区间内最大连续和

 

一、一个区间的最大子段和有三种情况

1、左子区间的最大子段和

2、右子区间的最大子段和

3、横跨左右子区间

 

二、每个结点需要维护的信息

1、区间和sum

2、从区间左端点开始的最大子段和lgss

3、从区间右端点开始的最大子段和rgss

4、区间最大子段和gss

 

三、建树

1、遇到叶子节点就输入数据

2、合并区间信息

sum：左右子区间的区间和相加

lgss：max（左子区间的lgss，左子区间的sum + 右子区间的lgss）

rgss：max（右子区间的rgss，右子区间的sum + 左子区间的rgss）

gss：max（max（左子区间的最大子段和，右子区间的最大子段和），左子区间的右起最大子段和 + 右子区间的左起最大子段和）

  1. const int maxn = 10005;
  2. int a[maxn];
  3. struct node {
  4. 	int sum, l, r, lmax, rmax, maxx;
  5. }tree[maxn<<2];
  6. node pushup(node a,node b) {
  7. 	node res;
  8. 	res.l = a.l;
  9. 	res.r = b.r;
  10. 	res.sum = a.sum + b.sum;
  11. 	res.lmax = max(a.lmax, a.sum + b.lmax);
  12. 	res.rmax = max(b.rmax, b.sum + a.rmax);
  13. 	res.maxx = max(max(a.maxx, b.maxx), a.rmax + b.lmax);
  14. 	return res;
  15. }
  16. void build(int l, int r, int rt) {
  17. 	tree[rt].l = l;
  18. 	tree[rt].r = r;
  19. 	if (l == r) {
  20. 		tree[rt].lmax = tree[rt].rmax = tree[rt].sum = tree[rt].maxx = a[l];
  21. 		return;
  22. 	}
  23. 	int mid= (l + r) >> 1;
  24. 	build(l, mid, rt <<1 );
  25. 	build(mid + 1, r, rt << 1 | 1);
  26. 	tree[rt]=pushup(tree[rt<<1],tree[rt<<1|1]);
  27. }
  28. node query(int L, int R, int rt) {
  29. 	if (L == tree[rt].l&&tree[rt].r == R) {
  30. 		return tree[rt];
  31. 	}
  32. 	int m = (tree[rt].l + tree[rt].r) >> 1;
  33. 	if (R <= m) return query(L, R, rt << 1);
  34. 	else if (L > m)  return query(L, R, rt << 1 | 1);
  35. 	else
  36. 		return pushup(query(L, m, rt << 1), query(m + 1, R, rt << 1 | 1));
  37. }
  38. int main() {
  39. 	int  n, q, c, b;
  40. 	scanf("%d", &n);
  41. 	for (int i = 1; i <= n; i++) {
  42. 		scanf("%d", &a[i]);
  43. 	}
  44. 	build(1, n, 1);
  45. 	scanf("%d", &q);
  46. 	while (q--) {
  47. 		scanf("%d%d", &c, &b);
  48. 		printf("%d\n", query(c, b, 1).maxx);
  49. 	}
  50. 	return 0;
  51. }

2.已知一开始有一个空序列，接下来有Q次操作，每次操作给出type、first和second三个值。当type为1时，意味着该操作属于第一种操作：往序列尾部添加first个second数。当type为2时，意味着该操作属于第二种操作：查询序列中第first小至第second小的数值之和（一共有(second - first + 1)个数被累加），并将结果对1000000007取模后输出。

 

分析：

sum: 区间数的值的和  num: 区间数的数量和  ,对于每次询问的first和second，我们找到第first个和第second个分别是哪两个数字，

如果两个数字不相同，那么就先算出分别取了多少个这两个数字，对于两个数字中间的数字和我们可以直接用线段树区间求和得到

 

代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #pragma warning(disable:4996)
  5. using namespace std;
  6. const int maxn = 2e5 + 5;
  7. const int mod = 1e9 + 7;
  8. typedef long long ll;
  9. struct node {
  10. 	ll x, y;
  11. }e[maxn];
  12. ll op[maxn];
  13. ll b[maxn], sum[maxn<<2],num[maxn<<2];
  14. ll num1[maxn];
  15. void update(ll rt, ll l, ll r, ll x, ll ans) {
  16. 	if (l == r) {
  17. 		sum[rt] = (sum[rt] + (ans*b[x]) % mod) % mod;
  18. 		num[rt] += ans;
  19. 		return;
  20. 	}
  21. 	ll mid = (l + r) >> 1;
  22. 	if (x <= mid) {
  23. 		update(rt << 1, l, mid, x, ans);
  24. 	}
  25. 	else {
  26. 		update(rt << 1 | 1, mid + 1, r, x, ans);
  27. 	}
  28. 	sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod;
  29. 	num[rt] = (num[rt << 1] + num[rt << 1 | 1]);
  30. }
  31. ll query(ll L, ll R, ll l, ll r, ll rt) {//区间查询[L,R]的数的值的和
  32. 	if (L <= l && R >= r) {
  33. 		return sum[rt]%mod;
  34. 	}
  35. 	ll mid = (l + r) >> 1;
  36. 	ll ans = 0;
  37. 	if (L <= mid) {
  38. 		ans = (ans+query(L, R, l, mid, rt << 1))%mod;
  39. 	}
  40. 	if (mid < R) {
  41. 		ans = (ans+query(L, R, mid + 1, r, rt << 1 | 1))%mod;
  42. 	}
  43. 	return ans;
  44. }
  45. ll query1(ll pos, ll l, ll r, ll rt) {//查询pos位于b数组的哪个位置
  46. 	if (num[rt] >= pos && num[rt] - num1[r] < pos)
  47. 		return r;//说明第pos小的数是b[r]
  48. 	ll mid = (l + r) >> 1;
  49. 	if (pos <= num[rt << 1]) {
  50. 		query1(pos, l, mid, rt << 1);
  51. 	}
  52. 	else {
  53. 		query1(pos - num[rt << 1], mid + 1, r, rt << 1 | 1);
  54. 	}
  55. }
  56. ll query2(ll L, ll R, ll l, ll r, ll rt) {//求区间[L,R]有多少个数字
  57. 	if (L <= l && R >= r) {
  58. 		return num[rt];
  59. 	}
  60. 	ll mid = (l + r) >> 1;
  61. 	ll ans = 0;
  62. 	if (L <= mid) {
  63. 		ans += query2(L, R, l, mid, rt << 1);
  64. 	}
  65. 	if(mid<R) {
  66. 		ans += query2(L, R, mid + 1, r, rt << 1 | 1);
  67. 	}
  68. 	return ans;
  69. }
  70. int main() {
  71. 	int n;
  72. 	scanf("%d", &n);
  73. 	int cnt = 0;
  74. 	for (int i = 1; i <= n; i++) {
  75. 		scanf("%lld%lld%lld", &op[i], &e[i].x, &e[i].y);
  76. 		if (op[i] == 1) {
  77. 			b[++cnt] = e[i].y;
  78. 		}
  79. 	}
  80. 	sort(b + 1, b + cnt + 1);
  81. 	for (int i = 1; i <= n; i++) {
  82. 		if (op[i] == 1) {
  83. 			ll m = lower_bound(b + 1, b + cnt + 1, e[i].y) - b;
  84. 			update(1, 1, cnt, m, e[i].x);
  85. 			num1[m] += e[i].x;
  86. 		}
  87. 		else {
  88. 			ll l = query1(e[i].x, 1, cnt, 1);
  89. 			ll r = query1(e[i].y, 1, cnt, 1);
  90. 			ll ans = 0;
  91. 			if (l == r) {
  92. 				ans = b[l] * (e[i].y - e[i].x + 1) % mod;
  93. 			}
  94. 			else {
  95. 				ll l = query1(e[i].x, 1, cnt, 1);
  96. 				ll r = query1(e[i].y, 1, cnt, 1);
  97. 				ll k1 = ((query2(1, l, 1, cnt, 1) - e[i].x + 1 + mod) % mod)*b[l] % mod;//l剩余的
  98. 				ll k2 = ((e[i].y - query2(1, r - 1, 1, cnt, 1) + mod) % mod)*b[r] % mod;///r剩余的
  99. 				ll k0 = query(l + 1, r - 1, 1, cnt, 1);//[l+1,r-1]整段区间的
  100. 				ans = (k1 + k2 + k0) % mod;
  101. 			}
  102. 			printf("%lld\n", ans);
  103. 		}
  104. 	}
  105. 	return 0;
  106. }

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

对于每个询问，输出一个整数表示答案。

 

题解

gcd(a,b)=gcd(a,b−a)

gcd(a,b,c)=gcd(a,b−a,c−b)

gcd(a1,a2,⋯,an)=gcd(a1,a2−a1,a3−a2,⋯,an−an−1)

知道了这个性质我们可以开一个B[  ] 数组，表示原序列的差分序列，用线段数维护B的区间最大公约数

对于询问“Q l r”等于求出gcd(a[l],query(1,l+1,r))

对于询问"C l r d"等于B[l] 加上d ，B[r+1] 减去d ，只需两次线段数的单点修改即可，对于原序列中A 的值，我们可以用一个“区间修改+单点查询”的树状数组来维护

 

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #pragma warning(disable:4996)
  5. using namespace std;
  6. const int maxn = 2e5 + 5;
  7. const int mod = 1e9 + 7;
  8. typedef long long ll;
  9. struct node {
  10. 	ll x, y;
  11. }e[maxn];
  12. ll op[maxn];
  13. ll b[maxn], sum[maxn<<2],num[maxn<<2];
  14. ll num1[maxn];
  15. void update(ll rt, ll l, ll r, ll x, ll ans) {
  16. 	if (l == r) {
  17. 		sum[rt] = (sum[rt] + (ans*b[x]) % mod) % mod;
  18. 		num[rt] += ans;
  19. 		return;
  20. 	}
  21. 	ll mid = (l + r) >> 1;
  22. 	if (x <= mid) {
  23. 		update(rt << 1, l, mid, x, ans);
  24. 	}
  25. 	else {
  26. 		update(rt << 1 | 1, mid + 1, r, x, ans);
  27. 	}
  28. 	sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod;
  29. 	num[rt] = (num[rt << 1] + num[rt << 1 | 1]);
  30. }
  31. ll query(ll L, ll R, ll l, ll r, ll rt) {//区间查询[L,R]的数的值的和
  32. 	if (L <= l && R >= r) {
  33. 		return sum[rt]%mod;
  34. 	}
  35. 	ll mid = (l + r) >> 1;
  36. 	ll ans = 0;
  37. 	if (L <= mid) {
  38. 		ans = (ans+query(L, R, l, mid, rt << 1))%mod;
  39. 	}
  40. 	if (mid < R) {
  41. 		ans = (ans+query(L, R, mid + 1, r, rt << 1 | 1))%mod;
  42. 	}
  43. 	return ans;
  44. }
  45. ll query1(ll pos, ll l, ll r, ll rt) {//查询pos位于b数组的哪个位置
  46. 	if (num[rt] >= pos && num[rt] - num1[r] < pos)
  47. 		return r;//说明第pos小的数是b[r]
  48. 	ll mid = (l + r) >> 1;
  49. 	if (pos <= num[rt << 1]) {
  50. 		query1(pos, l, mid, rt << 1);
  51. 	}
  52. 	else {
  53. 		query1(pos - num[rt << 1], mid + 1, r, rt << 1 | 1);
  54. 	}
  55. }
  56. ll query2(ll L, ll R, ll l, ll r, ll rt) {//求区间[L,R]有多少个数字
  57. 	if (L <= l && R >= r) {
  58. 		return num[rt];
  59. 	}
  60. 	ll mid = (l + r) >> 1;
  61. 	ll ans = 0;
  62. 	if (L <= mid) {
  63. 		ans += query2(L, R, l, mid, rt << 1);
  64. 	}
  65. 	if(mid<R) {
  66. 		ans += query2(L, R, mid + 1, r, rt << 1 | 1);
  67. 	}
  68. 	return ans;
  69. }
  70. int main() {
  71. 	int n;
  72. 	scanf("%d", &n);
  73. 	int cnt = 0;
  74. 	for (int i = 1; i <= n; i++) {
  75. 		scanf("%lld%lld%lld", &op[i], &e[i].x, &e[i].y);
  76. 		if (op[i] == 1) {
  77. 			b[++cnt] = e[i].y;
  78. 		}
  79. 	}
  80. 	sort(b + 1, b + cnt + 1);
  81. 	for (int i = 1; i <= n; i++) {
  82. 		if (op[i] == 1) {
  83. 			ll m = lower_bound(b + 1, b + cnt + 1, e[i].y) - b;
  84. 			update(1, 1, cnt, m, e[i].x);
  85. 			num1[m] += e[i].x;
  86. 		}
  87. 		else {
  88. 			ll l = query1(e[i].x, 1, cnt, 1);
  89. 			ll r = query1(e[i].y, 1, cnt, 1);
  90. 			ll ans = 0;
  91. 			if (l == r) {
  92. 				ans = b[l] * (e[i].y - e[i].x + 1) % mod;
  93. 			}
  94. 			else {
  95. 				ll l = query1(e[i].x, 1, cnt, 1);
  96. 				ll r = query1(e[i].y, 1, cnt, 1);
  97. 				ll k1 = ((query2(1, l, 1, cnt, 1) - e[i].x + 1 + mod) % mod)*b[l] % mod;//l剩余的
  98. 				ll k2 = ((e[i].y - query2(1, r - 1, 1, cnt, 1) + mod) % mod)*b[r] % mod;///r剩余的
  99. 				ll k0 = query(l + 1, r - 1, 1, cnt, 1);//[l+1,r-1]整段区间的
  100. 				ans = (k1 + k2 + k0) % mod;
  101. 			}
  102. 			printf("%lld\n", ans);
  103. 		}
  104. 	}
  105. 	return 0;
  106. }

在i右侧的所有满足a[j]>=a[i]+m 中最大的j−i−1 ，若不存在这样的数则值为−1。输出每个元素的愤怒值。

 

思路：用线段树维护区间最大值。那么要查询的其实就是[i+1,n] 内满足a[j]>=a[i]+m 的最大的j，因此考虑优先查询右子树，最后返回下标即可。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<iostream>
  5. using namespace std;
  6. const int maxn = 500005;
  7. #pragma warning(disable:4996)
  8. typedef long long ll;
  9. struct node {
  10. 	ll l, r, maxx;
  11. }tree[maxn];
  12. ll a[maxn];
  13. void build(int l, int r, int rt) {
  14. 	tree[rt].l = l;
  15. 	tree[rt].r = r;
  16. 	if (l == r) {
  17. 		tree[rt].maxx = a[l];
  18. 		return;
  19. 	}
  20. 	int mid = (l + r) >> 1;
  21. 	build(l, mid,rt<<1);
  22. 	build(mid + 1, r, rt << 1 | 1);
  23. 	tree[rt].maxx = max(tree[rt << 1].maxx, tree[rt << 1 | 1].maxx);
  24. }
  25. ll query(int l, int r, int rt, ll v) {
  26. 	int mid = (tree[rt].l + tree[rt].r) >> 1;
  27. 	if (tree[rt].l == l && tree[rt].r == r) {
  28. 		if (tree[rt].maxx < v) {
  29. 			return -1;
  30. 		}
  31. 		if (tree[rt].l == tree[rt].r) {
  32. 			return l;
  33. 		}
  34. 		if (tree[rt << 1 | 1].maxx >= v) {
  35. 			return query(mid + 1, r, rt << 1 | 1, v);
  36. 		}
  37. 		else if (tree[rt << 1].maxx > v) {
  38. 			return query(l, mid, rt << 1, v);
  39. 		}
  40. 		else {
  41. 			return -1;
  42. 		}
  43. 	}
  44. 	if (r <= mid) {
  45. 		return query(l, r, rt << 1, v);
  46. 	}
  47. 	else if (l > mid) {
  48. 		return query(l, r, rt << 1 | 1, v);
  49. 	}
  50. 	else {
  51. 		ll ans1 = query(l, mid, rt << 1, v);
  52. 		ll ans2 = query(mid + 1, r, rt << 1 | 1, v);
  53. 		if (ans2 != -1) {
  54. 			return ans2;
  55. 		}
  56. 		else if (ans1 != -1) {
  57. 			return ans1;
  58. 		}
  59. 		else {
  60. 			return -1;
  61. 		}
  62. 	}
  63. }
  64. int main() {
  65. 	int n, m;
  66. 	scanf("%d%d", &n, &m);
  67. 	for (int i = 1; i <= n; i++) {
  68. 		scanf("%lld", &a[i]);
  69. 	}
  70. 	build(1, n, 1);
  71. 	for (int i = 1; i <= n; i++) {
  72. 		if (i == n) {
  73. 			printf("-1\n");
  74. 		}
  75. 		else {
  76. 			ll ans = query(i + 1, n, 1, a[i]+m);
  77. 			if (ans != -1) {
  78. 				printf("%lld ", ans-i-1);
  79. 			}
  80. 			else {
  81. 				printf("-1 ");
  82. 			}
  83. 		}
  84. 	}
  85. 	return 0;
  86. }

给你一个区间，要支持两种区间操作。

第一种操作是单点更新，第二种操作是询问某个区间是否可以去掉一个元素或者不去使这段区间的gcd为x 的倍数。

分析：

线段树来做，做更改时直接做，每个点存gcd，然后查询时，我们判断区间不满足时就判断到点，并让cnt++，如果cnt大于1直接return（只能有一个数字不是x的倍数）。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<string>
  5. #include<cmath>
  6. #include<queue>
  7. #include<vector>
  8. #include<iostream>
  9. #pragma warning(disable:4996)
  10. using namespace std;
  11. typedef long long ll;
  12. const int maxn = 300005;
  13. int n;
  14. int a[maxn];
  15. int tree[maxn * 4];
  16. int gcd(int x, int y) {
  17. 	if (y == 0)
  18. 		return x;
  19. 	else {
  20. 		return gcd(y, x%y);
  21. 	}
  22. }
  23. int cnt;
  24. void pushup(int rt) {
  25. 	tree[rt] = gcd(tree[rt << 1], tree[rt << 1 | 1]);
  26. }
  27. void build(int l, int r, int rt) {
  28. 	if (l == r) {
  29. 		tree[rt] = a[l];
  30. 		return;
  31. 	}
  32. 	int mid = (l + r) >> 1;
  33. 	build(l, mid, rt << 1);
  34. 	build(mid + 1, r, rt << 1 | 1);
  35. 	pushup(rt);
  36. }
  37. void update(int l, int r, int pos, int k, int rt) {
  38. 	if (l==r) {
  39. 		tree[rt] = k;
  40. 		return;
  41. 	}
  42. 	int mid = (l + r) >> 1;
  43. 	if (pos<=mid ) {
  44. 		update(l, mid, pos, k, rt << 1);
  45. 	}
  46. 	else {
  47. 		update(mid + 1, r, pos,k, rt << 1 | 1);
  48. 	}
  49. 	pushup(rt);
  50. }
  51. void query(int l, int r, int L, int R, int k, int rt) {
  52. 	if (cnt > 1)
  53. 		return;
  54. 	if (l == r) {
  55. 		cnt++;
  56. 		return;
  57. 	}
  58. 	int mid = (l + r) >> 1;
  59. 	if (L <= mid&&tree[rt<<1]%k!=0){
  60. 		query(l, mid, L, R, k, rt << 1);
  61. 	}
  62. 	if (R > mid&&tree[rt << 1 | 1] % k != 0) {
  63. 		query(mid + 1, r, L, R, k, rt << 1 | 1);
  64. 	}
  65. }
  66. int main() {
  67. 	scanf("%d", &n);
  68. 	for (int i = 1; i <= n; i++) {
  69. 		scanf("%d", &a[i]);
  70. 	}
  71. 	build(1, n, 1);
  72. 	int m;
  73. 	scanf("%d", &m);
  74. 	while (m--) {
  75. 		int x, l, r, k;
  76. 		scanf("%d", &x);
  77. 		if (x == 2) {
  78. 			scanf("%d%d", &l, &k);
  79. 			update(1, n, l, k, 1);
  80. 		}
  81. 		else {
  82. 			scanf("%d%d%d", &l, &r, &k);
  83. 			cnt = 0;
  84. 			query(1, n, l, r, k, 1);
  85. 			if (cnt > 1) {
  86. 				printf("NO\n");
  87. 			}
  88. 			else {
  89. 				printf("YES\n");
  90. 			}
  91. 		}
  92. 	}
  93. 	return 0;
  94. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/180116
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号