《算法竞赛进阶指南》0x00树状数组
2022/1/8 11:04:04
本文主要是介绍《算法竞赛进阶指南》0x00树状数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
清点人数
#include <iostream> #include <cstdio> using namespace std; const int N = 5e5 + 10; int n, k, c[N]; //c为原序列的树状数组 int lowbit(int x) { return x & -x; } //将原序列下标为pos的元素值增加x,改变相应的c数组的值 void update(int pos, int x) { for (int i = pos; i <= n; i += lowbit(i)) c[i] += x; } //对原序列前pos项求和 int sum(int pos) { int res = 0; for (int i = pos; i > 0; i -= lowbit(i)) res += c[i]; return res; } int main() { scanf("%d%d", &n, &k); while (k --) { char op[2]; //注意字符变量的输入方式 int m, p; scanf("%s", &op); if (op[0] == 'A') scanf("%d", &m), printf("%d\n", sum(m)); if (op[0] == 'B') scanf("%d%d", &m, &p), update(m, p); if (op[0] == 'C') scanf("%d%d", &m, &p), update(m, -p); } return 0; }
数列操作
#include <iostream> #include <cstdio> using namespace std; const int N = 1e5 + 10; int n, m, x, c[N]; //c为原序列的树状数组 int lowbit(int x) { return x & -x; } //将原序列下标为pos的元素值增加x,改变相应的c数组的值 void update(int pos, int x) { for (int i = pos; i <= n; i += lowbit(i)) c[i] += x; } //对原序列前pos项求和 int sum(int pos) { int res = 0; for (int i = pos; i > 0; i -= lowbit(i)) res += c[i]; return res; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++) scanf("%d", &x), update(i, x); while (m --) { int k, a, b; scanf("%d%d%d", &k, &a, &b); //sum(b) - sum(a - 1)即为区间[a, b]的和 if (k == 0) printf("%d\n", sum(b) - sum(a - 1)); else update(a, b); } return 0; }
简单题
#include <iostream> #include <cstdio> using namespace std; const int N = 1e5 + 10; int n, m, c[N]; int lowbit(int x) { return x & -x; } void update(int pos, int x) { for (int i = pos; i <= n; i += lowbit(i)) c[i] += x; } int sum(int pos) { int res = 0; for (int i = pos; i > 0; i -= lowbit(i)) res += c[i]; return res; } int main() { scanf("%d%d", &n, &m); while (m --) { int t, l, r; scanf("%d", &t); if (t == 1) scanf("%d%d", &l, &r), update(l, 1), update(r + 1, -1); else scanf("%d", &l), printf("%d\n", sum(l) % 2); } return 0; }
数星星Stars
#include <iostream> #include <cstdio> using namespace std; const int N = 2e4 + 10, MAXX = 32000 + 10; int n, m, c[MAXX], h[N]; int lowbit(int x) { return x & -x; } void update(int pos, int x) { for (int i = pos; i <= MAXX; i += lowbit(i)) c[i] += x; } int sum(int pos) { int res = 0; for (int i = pos; i > 0; i -= lowbit(i)) res += c[i]; return res; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++) { int x, y; scanf("%d%d", &x, &y); x ++; //根据题意,x有可能为0 int t = sum(x); h[t] ++; update(x, 1); } for (int i = 0; i < n; i ++) printf("%d\n", h[i]); return 0; }
校门外的树
#include <iostream> #include <cstdio> using namespace std; const int N = 5e4 + 10; int n, m, c1[N], c2[N]; int lowbit(int x) { return x & -x; } void update1(int pos, int x) { for (int i = pos; i <= n; i += lowbit(i)) c1[i] += x; } void update2(int pos, int x) { for (int i = pos; i <= n; i += lowbit(i)) c2[i] += x; } int sum1(int pos) { int res = 0; for (int i = pos; i > 0; i -= lowbit(i)) res += c1[i]; return res; } int sum2(int pos) { int res = 0; for (int i = pos; i > 0; i -= lowbit(i)) res += c2[i]; return res; } int main() { scanf("%d%d", &n, &m); while (m --) { int k, l, r; scanf("%d%d%d", &k, &l, &r); if (k == 1) update1(l, 1), update2(r, 1); else printf("%d\n", sum1(r) - sum2(l - 1)); } return 0; }
这篇关于《算法竞赛进阶指南》0x00树状数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南