树状数组求区间最大值(树状数组)(复习)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了树状数组求区间最大值(树状数组)(复习)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1934字，纯文字阅读大概需要3分钟。
内容图文
如题。
当遇到单点更新时，树状数组往往比线段树更实用。
算法:
设原数序列为a[i]，最大值为h[i](树状数组)。
1。单点更新：
直接更新a[i]，然后再更新h[i]。若h[i]的值有可能改变的，则表示区间一定包含i结点。那么就两层lowbit更新所有可能的h。
单点更新时间复杂度O(logn*logn)
1
void update(int x)
2{
3while(x<=n)
4 {
5 h[x]=a[x];
6for(int i=1;i<lowbit(x);i<<=1)
7 h[x]=max(h[x],h[x-i]);
8 x+=lowbit(x);
9 }
10return ;
11 }
2。区间查询最大值：
设要查询的区间为[L,R]，那么就从h[R]开始找，要找[L,R]内的所有区间。所以依然是两层lowbit，然后R向前跳直到跳到L前面。
区间查询最大值时间复杂度O(logn*logn)
1
void findans(int begin,int end)
2{
3int ans=0;
4while(end>=begin)
5 {
6 ans=max(ans,h[end]);
7 end--;
8for(;end-lowbit(end)>=begin;end-=lowbit(end))
9 ans=max(ans,h[end]);
10 }
1112 printf("%d\n",ans);
13return ;
14 }
相关试题:hdu1754(单点修改，区间求最大值)
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<cmath>
5usingnamespace std;
6constint maxn=300005;
7int h[maxn],a[maxn];
8int n,m;
9int lowbit(int x)
10{
11return x&(-x);
12}
13void update(int x)
14{
15while(x<=n)
16 {
17 h[x]=a[x];
18for(int i=1;i<lowbit(x);i<<=1)
19 h[x]=max(h[x],h[x-i]);
20 x+=lowbit(x);
21 }
22return ;
23}
24void findans(int begin,int end)
25{
26int ans=0;
27while(end>=begin)
28 {
29 ans=max(ans,a[end]);
30 end--;
31for(;end-lowbit(end)>=begin;end-=lowbit(end))
32 ans=max(ans,h[end]);
33 }
3435 printf("%d\n",ans);
36return ;
37}
38int main()
39{
40//freopen("in.txt","r",stdin);
41//freopen("out.txt","w",stdout);42while(scanf("%d%d",&n,&m)==2)
43 {
44 memset(h,0,sizeof(h));
45for(int i=1;i<=n;i++)
46 {
47 scanf("%d",&a[i]);
48 update(i);
49 }
50for(int i=1;i<=m;i++)
51 {
52char c=getchar();
53while(c!=‘Q‘&&c!=‘U‘)c=getchar();
54if(c==‘U‘)//update55 {
56int y,z;
57 scanf("%d%d",&y,&z);
58 a[y]=z;
59 update(y);
60continue;
61 }
62if(c==‘Q‘)//findans63 {
64int y,z;
65 scanf("%d%d",&y,&z);
66 findans(y,z);
67continue;
68 }
69 }
70 }
7172return0;
73 }
原文：http://www.cnblogs.com/937337156Zhang/p/6072330.html
内容总结
以上是互联网集市为您收集整理的树状数组求区间最大值(树状数组)(复习)全部内容，希望文章能够帮你解决树状数组求区间最大值(树状数组)(复习)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。