I Hate It（hdoj 树状数组求区间最大值）

原题：http://acm.hdu.edu.cn/showproblem.php?pid=1754

题解参考于：https://blog.csdn.net/mosquito_zm/article/details/76422738

依旧不懂时间复杂度是怎么求得的。不懂为啥一开始的时间复杂度为O（n*log n）

代码如下

/**
**	不会就抄抄别人的https://blog.csdn.net/mosquito_zm/article/details/76422738 
**/ 

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int MAXN=3e5;
int a[MAXN],h[MAXN];
int n,m;

int lowbit(int x){
	return x&(-x);
}
//维护区间最大值的算法，时间复杂度为O（n*logn） 
//即当要更新一个数时，把h[]清零，然后用a[]
//数组去更新b[] 
void update1(int i,int val){
	while(i<=n){
		h[i]=max(h[i],val);
		i+=lowbit(i);
	}
}

//O((logn)^2)算法
// 因为y经过Logn次变换以后，其与x不同的最高位至少下降了1位，所以最多进行(logn)^2次变换

//可以发现：对于x，可以转移到x的只有，x-2^0，x-2^1，x-2^2，.......，x-2^k 
//（k满足2^k < lowbit(x)且2^(k+1)>=lowbit(x)）

void update(int x){
	int lx,i;
	while(x<=n){
		h[x]=a[x];
		lx=lowbit(x);
		for(int i=1;i<lx;i<<=1){//i<<=1变量i左移一位 
			h[x]=max(h[x],h[x-i]); 
		}
		x+=lowbit(x);
	}
}
int query(int x,int y){
	int ans=0;
	while(y>=x){
		ans=max(a[y],ans);
		y--;
		for(;y-lowbit(y)>=x;y-=lowbit(y)){
			ans=max(h[y],ans);
		}
	}
	return ans;
}
int main(){
	int i,j,x,y,ans;
	char c ;
	while(scanf("%d%d",&n,&m)!=EOF){
		for(int i=1;i<=n;i++){
			h[i]=0;
		}		
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			update(i);
		}
		for(int i=1;i<=m;i++){
			scanf("%s",&c);	scanf("%d%d",&x,&y);
			if(c=='Q'){			
				cout<<query(x,y)<<endl;
			}else{
				a[x]=y;
				update(x);
			}
		}
	}
	
	return 0;
}

最后

以上就是活泼蜡烛为你收集整理的I Hate It（hdoj 树状数组求区间最大值）的全部内容，希望文章能够帮你解决I Hate It（hdoj 树状数组求区间最大值）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。