算法提高课 第四章 数据结构之树状数组
2022/9/5 1:22:51
本文主要是介绍算法提高课 第四章 数据结构之树状数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、介绍
功能
- 快速求前缀和 O(logn)
- 修改某一个数 O(logn)
原理
c[x]:以x结尾的长度lowbit(x)的所有数的和
父节点找所有子节点(求和操作):c[x] = a[x] + c[x-1] + ... + c[lowbit(x-1)]
,x为偶数时,每一次去掉最后一个1;x为奇数时,没有子节点
子节点找父节点(修改操作):p = x + lowbit(x)
,修改当前结点时,一连串的与该结点有关的父节点都要被修改
建立
题目
241. 楼兰图腾
思路:个数统计+树状数组(O(nlogn))
- y1~yn是1到n的一个全排列,对于某个位置的数而言,左边比它大的数的个数与右边比它大的数的个数的乘积就是组成'V'型的个数。
- 同理,左边比它小的数的个数与右边比它小的数的个数的乘积就是组成'^'型的个数。
- 因此,我们可以维护一个lower和upper数组,lower[i]表示比a[i]小的个数,upper[i]表示比a[i]大的个数。从左到右,边统计边查询,这样lower和upper就表示某个数左边比它大或小的数的个数。使用树状数组可以快速求出某个区间的和与修改某个数,c[x]来表示x出现的次数,sum(n)-sum(x)表示比x大的数的个数,sum(x-1)表示小于x的数的个数。
- 同理,从右往左边统计边查询,可以处理处某个数右边比它大或小的数的个数。
题解
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 2e5 + 20; int n; int a[N]; int tr[N]; int lower[N],upper[N]; inline 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 += (LL)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 x = a[i]; upper[i] = sum(n) - sum(x-1);//查询左边比a[i]大的数的个数 lower[i] = sum(x-1);//查询左边比a[i]小的数的个数 add(x,1);//添加a[i] } LL ans1 = 0,ans2 = 0; memset(tr,0,sizeof tr); //清空线段树 for(int i = n;i>=1;i--)//从右往左求右边比a[i]大 or 小的数 { int x = a[i]; ans1 += (LL)upper[i]*(sum(n) - sum(x));//左边大的乘以右边大的就是构成V的个数 ans2 += (LL)lower[i]*sum(x-1);//左边小的乘以右边小的就是构成^的个数 add(x,1);//添加a[i] } printf("%lld %lld\n",ans1,ans2); return 0; }
242. 一个简单的整数问题
思路:树状差分数组 O(nlogn)
- 题目中有区间修改,单点查询,符合差分数组的性质,而差分单点查询本质操作是求前缀和(O(n)),一定超时,因为差分的区间修改本质是单点修改,我们可以把差分数组构造成树状数组,使得所有操作为O(logn)的
题解
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 10; int tr[N];//差分树状数组:支持区间/单点查询,区间/单点修改 int n,m; 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; } void insert(int l,int r,int c) //差分的插入操作均为单点修改,符合树状数组的性质 { add(l,c);// tr[l] += c; add(r+1,-c); //tr[r+1] -= c; return; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) { int x; scanf("%d", &x); insert(i,i,x); } while (m -- ) { char op[2]; int l,r,d,x; scanf("%s", &op); if(op[0] == 'C') { scanf("%d%d%d", &l, &r,&d); insert(l,r,d); } else { scanf("%d", &x); cout<<sum(x)<<endl;//通过差分还原某个数的操作是区间求和,符合树状数组性质 } } return 0; }
243. 一个简单的整数问题2
思路
- 题目中有区间修改,必须使用差分数组;有区间求和,必须使用树状数组
- 原数组的区间和相当于先对差分数组1~i求和还原出原数组,再对原数组求和,O(n^2)一定会超时
- 我们发现了对原数组1~n求和的公式
(n+1)*(a1+…+an) - (1*a1+…n*an)
,因此我们可以构造两个树状数组分别维护ai与i*ai的差分
题解
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 1e5 + 10; int n,m; LL tr1[N],tr2[N]; int lowbit(int x) { return x & -x; } void add(LL tr[],int x,LL c) //树状数组单点修改 { for(int i = x;i<=n;i+=lowbit(i)) { tr[i] += c; } } LL sum(LL tr[],int x) //树状数组区间查询 { LL res = 0; for(int i = x;i;i-=lowbit(i)) { res += (LL)tr[i]; } return res; } void insert(int l,int r,LL c) //差分数组区间修改 { add(tr1,l,c); add(tr1,r+1,-c); add(tr2,l,l*c); add(tr2,r+1,-(r+1)*c); } LL get(int x) //求和公式 { LL res = (LL)(x+1)*sum(tr1,x)-sum(tr2,x); return res; } int main() { scanf("%d%d", &n, &m); for(int i = 1;i<=n;i++) { int x; scanf("%d", &x); insert(i,i,x); } while (m -- ) { char op[2]; int l,r,d; scanf("%s", op); if(op[0] == 'C') { scanf("%d%d%d", &l,&r,&d); insert(l,r,d); } else { scanf("%d%d", &l,&r); cout<< get(r) - get(l-1) <<endl; } } return 0; }
244. 谜一样的牛
思路:树状数组+二分 O(n(logn)^2)
先思考常规做法:数组A[i]表示前面有A[i]个数小于第i个位置的数,而A[i]是1-n的全排列,故我们可以A[i]从右往左遍历,对于第i个数而言,前i-1个数中有a[i]个比它小,即在这剩余的数中它是第a[i]+1小的,排序选出第a[i]+1个小的数,并从剩余的数中删除。时间复杂度为O(n^2logn),显然不符合要求。
树状数组优化:tr[i]表示当前i的个数(0 or 1),从右向左,二分查找出最小的x,使得sum[x]=a[i]+1,sum[x]表示1-x中有多少个剩余的数可用,因为是最小的x,所以tr[x]一定是1,且x一定是1-x中第a[i]+1小的数。x即为所求。最后一定要从tr中删除x
题解
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 10; int a[N],n; int tr[N];//tr[x]:表示当前x的可用的个数 int ans[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; } return; } int sum(int x) { int res = 0; for(int i = x;i;i-=lowbit(i)) { res += tr[i]; } return res; } int main() { cin>>n; for(int i = 2;i<=n;i++) //注意从2开始循环 { cin>>a[i]; } for(int i = 1;i<=n;i++) add(i,1); //初始化为1,可用 for(int i = n;i;i--) { int l = 1,r = n,x = a[i] + 1; while(l<r) //二分找出最小的x,使得sum(x) = a[i] + 1 { int mid = l+r>>1; if(sum(mid) >= x) r = mid; else l = mid + 1; } ans[i] = r; add(r,-1); //删除x } for (int i = 1; i <= n; i ++ ) cout<<ans[i]<<endl; return 0; }
这篇关于算法提高课 第四章 数据结构之树状数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署