树状数组求区间最大值(转载)

[数组的含义]

1、在维护和查询区间和的算法中，h[x]中储存的是[x，x-lowbit(x)+1]中每个数的和 .

2、在求区间最值的算法中，h[x]储存的是[x，x-lowbit(x)+1]中每个数的最大值。

求区间最值的算法中还有一个a[i]数组，表示第i个数是多少,也就是原数组。

[单点修改后的更新]

1、在维护区间和的算法中，是这样维护单点修改的

void update(int i,int v){
	//区间和更新
	while(i<=n){
		h[i]+=v;
		i+=lowbit(i) ;
	}
}

2、在来看维护区间最大值的算法，我们先看一整段区间[1，n]都需要初始化的情况。（即 h[] 数组都为0，现在需要用 a[] 数组更新 h[] 数组）

void updata(int i, int val)
{
	while (i <= n)
	{
		h[i] = max(h[i], val);
		i += lowbit(i);
	}
}

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

举例:

若 x = 1010000

= 1001000 + lowbit(1001000) = 1001000 + 1000 = 1001000 + 2^3

= 1001100 + lowbit(1001100) = 1001100 + 100 = 1001100 + 2^2

= 1001110 + lowbit(1001110) = 1001110 + 10 = 1001110 + 2^1

= 1001111 + lowbit(1001111) = 1001111 + 1 = 1001111 + 2^0

所以对于每一个h[i]，在保证h[1...i-1]都正确的前提下，要重新计算h[i]值的时间复杂度是O（logn），具体方法如下：

	h[x] = a[x];
	lx = lowbit(x);
	for (i=1; i<lx; i<<=1)
	h[x] = max(h[x], h[x-i]);
	x += lowbit(x);

这样，我们就可以得到一个和树状数组维护区间合算法很像的算法

void updata(int x)
{
	int lx, i;
	while (x <= n)
	{
		h[x] = a[x];
		lx = lowbit(x);
		for (i=1; i<lx; i<<=1)
			h[x] = max(h[x], h[x-i]);
		x += lowbit(x);
	}		
}

这个算法的时间复杂度是O((logn)^2)，所以现在就可以在O（(logn)^2）的时间内完成最值的区间维护了。

[区间查询]

1、树状数组求区间合的算法是这样子的：

int query(int i)
{
	int ans = 0;
	while (i > 0)
	{
		ans += h[i];
		i -= lowbit(i);
	}
	return ans;
}

2、树状数组求区间最大值：

直接照搬求区间合的方法显然是不行的。

因为区间合中，要查询[x,y]的区间合，是求出[1,x-1]的合与[1,y]的合，然后相减就得出了[x,y]区间的合。

而区间最值是没有这个性质的，所以只能够换一个思路。

设query(x,y)，表示[x，y]区间的最大值

因为h[y]表示的是[y,y-lowbit(y)+1]的最大值。

所以，可以这样求解：

若y-lowbit(y) > x ，则query(x,y) = max( h[y] , query(x, y-lowbit(y)) );

若y-lowbit(y) <=x，则query(x,y) = max( a[y] , query(x, y-1);

这个递归求解是可以求出解的，且可以证明这样求解的时间复杂度是O（(logn)^2）

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;
}

时间复杂度的证明：（换成二进制来看）

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

举例：

y = 1010000

x = 1000001

1010000

=> 1001111 => 1001110 =>1001100 =>1001000

=>1000111 => 1000110 => 1000100

=> 1000011 = > 1000010

=>1000001

=>1000000 < 1000001
 

模板题: I Hate It HDU - 1754

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#define Swap(a,b)  a ^= b ^= a ^= b
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std ;
typedef long long LL;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
const int MAX = 3e5;
const int inf = 0xffffff;
const LL mod = 1e9+7 ;
 
int minn = 0x3f3f3f3f ;
int maxx = -0x3f3f3f3f;
// ----+-+------------------------
int n ;
int a[MAX] ;
int c[MAX] ;
int lowbit(int x){return x&(-x);}
void update(int i,int v){
	//区间和更新
	while(i<=n){
		c[i]+=v;
		i+=lowbit(i) ;
	}
}
void Update(int x){
	//区间最值更新
	int lx ,i ;
	while(x<=n){
		c[x] = a[x];
		lx = lowbit(x) ;
		for(i = 1 ;i<lx;i<<=1){
			c[x] = max(c[x],c[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(c[y],ans) ;
		}
	}
	return ans ;
}
int sum(int i){
	//区间和
	int ans = 0 ;
	while(i){
		ans+=c[i] ;
		i-=lowbit(i) ;
	}
	return ans ;
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
	int m ;
	while(scanf("%d%d",&n,&m)!=EOF){
		for(int i = 1 ;i<=n;i++){
			c[i] = 0 ;
		}
		for(int i = 1; i<=n ;i++){
			scanf("%d",&a[i]);
			Update(i) ;
		}
	// ---------------------------
		while(m--){
			char op[5]  ;
			int x ,y ;
			int ans ;
			scanf("%s",op);
			if(op[0]=='Q'){ // 查询
				scanf("%d%d",&x,&y);
				ans = query(x,y) ;
				printf("%d\n",ans);
			}
			else{
				scanf("%d%d",&x,&y);
				a[x] = y ;
				Update(x);
			}
		}
	}
    return 0;
}