网站开发环境与工具,企业网站优化方案,小广告网站,谷德设计网打不开知识概览 树状数组有两个作用#xff1a; 快速求前缀和 时间复杂度O(log(n))修改某一个数 时间复杂度O(log(n)) 例题展示 1. 单点修改#xff0c;区间查询 题目链接
活动 - AcWing本活动组织刷《算法竞赛进阶指南》#xff0c;系统学习各种编程算法。主要面向…知识概览 树状数组有两个作用 快速求前缀和 时间复杂度O(log(n))修改某一个数 时间复杂度O(log(n)) 例题展示
1. 单点修改区间查询 题目链接
活动 - AcWing本活动组织刷《算法竞赛进阶指南》系统学习各种编程算法。主要面向有一定编程基础的同学。https://www.acwing.com/problem/content/description/243/
题解 涉及单点修改和求前缀和并且要求时间复杂度小可以用树状数组。 代码
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 200010;int n;
int a[N];
int tr[N];
int Greater[N], lower[N];int lowbit(int x)
{return x -x;
}void add(int x, int c)
{for (int i x; i n; i lowbit(i)) tr[i] c;
}int sum(int x)
{int res 0;for (int i x; i; i - lowbit(i)) res tr[i];return res;
}int main()
{scanf(%d, n);for (int i 1; i n; i) scanf(%d, a[i]);for (int i 1; i n; i){int y a[i];Greater[i] sum(n) - sum(y);lower[i] sum(y - 1);add(y, 1); //将y加入树状数组即数字y出现1次}memset(tr, 0, sizeof tr);LL res1 0, res2 0;for (int i n; i; i--){int y a[i];res1 Greater[i] * (LL)(sum(n) - sum(y));res2 lower[i] * (LL)(sum(y - 1));add(y, 1); //将y加入树状数组即数字y出现1次}printf(%lld %lld\n, res1, res2);return 0;
} 2.区间修改单点查询 题目链接
活动 - AcWing本活动组织刷《算法竞赛进阶指南》系统学习各种编程算法。主要面向有一定编程基础的同学。https://www.acwing.com/problem/content/248/
题解 需要用到差分数组区间修改可以转化成对差分数组的单点修改单点查询可以转化成对差分数组求前缀和这样就可以转化成经典的树状数组操作。 代码
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 100010;int n, m;
int a[N];
LL tr[N];int lowbit(int x)
{return x -x;
}void add(int x, int c)
{for (int i x; i n; i lowbit(i)) tr[i] c;
}LL sum(int x)
{LL res 0;for (int i x; i; i - lowbit(i)) res tr[i];return res;
}int main()
{scanf(%d%d, n, m);for (int i 1; i n; i) scanf(%d, a[i]);for (int i 1; i n; i) add(i, a[i] - a[i - 1]);while (m--){char op[2];int l, r, d;scanf(%s%d, op, l);if (*op C){scanf(%d%d, r, d);add(l, d), add(r 1, -d);}else{printf(%lld\n, sum(l));}}return 0;
} 参考资料
AcWing算法提高课
