首页 > 代码库 > 树状数组求区间最大值(树状数组)(复习)
树状数组求区间最大值(树状数组)(复习)
如题。
当遇到单点更新时，树状数组往往比线段树更实用。
算法:
设原数序列为a[i]，最大值为h[i](树状数组)。
1。单点更新：
直接更新a[i]，然后再更新h[i]。若h[i]的值有可能改变的，则表示区间一定包含i结点。那么就两层lowbit更新所有可能的h。
单点更新时间复杂度O(logn*logn)
1 void update(int x) 2 { 3 while(x<=n) 4 { 5 h[x]=a[x]; 6 for(int i=1;i<lowbit(x);i<<=1) 7 h[x]=max(h[x],h[x-i]); 8 x+=lowbit(x); 9 }10 return ;11 }
2。区间查询最大值：
设要查询的区间为[L,R]，那么就从h[R]开始找，要找[L,R]内的所有区间。所以依然是两层lowbit，然后R向前跳直到跳到L前面。
区间查询最大值时间复杂度O(logn*logn)
1 void findans(int begin,int end) 2 { 3 int ans=0; 4 while(end>=begin) 5 { 6 ans=max(ans,h[end]); 7 end--; 8 for(;end-lowbit(end)>=begin;end-=lowbit(end)) 9 ans=max(ans,h[end]);10 }11 12 printf("%d\n",ans);13 return ;14 }
相关试题:hdu1754(单点修改，区间求最大值)
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int maxn=300005; 7 int h[maxn],a[maxn]; 8 int n,m; 9 int lowbit(int x)10 {11 return x&(-x);12 }13 void update(int x)14 {15 while(x<=n)16 {17 h[x]=a[x];18 for(int i=1;i<lowbit(x);i<<=1)19 h[x]=max(h[x],h[x-i]);20 x+=lowbit(x);21 }22 return ;23 }24 void findans(int begin,int end)25 {26 int ans=0;27 while(end>=begin)28 {29 ans=max(ans,a[end]);30 end--;31 for(;end-lowbit(end)>=begin;end-=lowbit(end))32 ans=max(ans,h[end]);33 }34 35 printf("%d\n",ans);36 return ;37 }38 int main()39 {40 //freopen("in.txt","r",stdin);41 //freopen("out.txt","w",stdout);42 while(scanf("%d%d",&n,&m)==2)43 {44 memset(h,0,sizeof(h));45 for(int i=1;i<=n;i++)46 {47 scanf("%d",&a[i]);48 update(i);49 }50 for(int i=1;i<=m;i++)51 {52 char c=getchar();53 while(c!=‘Q‘&&c!=‘U‘)c=getchar();54 if(c==‘U‘)//update55 {56 int y,z;57 scanf("%d%d",&y,&z);58 a[y]=z;59 update(y);60 continue; 61 }62 if(c==‘Q‘)//findans63 {64 int y,z;65 scanf("%d%d",&y,&z);66 findans(y,z);67 continue;68 }69 }70 }71 72 return 0;73 }
树状数组求区间最大值(树状数组)(复习)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。