树状数组维护区间最值

\(update : 2022.2.1\)
学习

没错 , 树状数组也能维护区间最值.(单点修改 , 区间查询)

不过这种写法要对树状数组维护的区间要有一定的理解.

主要是理解 tree[x] 维护的区间 [x - lowbit(x) , x] 的最值

单点修改

//将 a[x] 修改为 y.
void updata(int x,int y){
	tree[x] = a[x] = y ; // 这里我的思考与原作有冲突.
	while( x<= n){
		//tree[x] = y ; 原作在这里加上了更新.
		int low = lowbit(x);
		for(i=1;i>=1? , 去观察树状数组维护的区间[x-lowbit(x),x] , 都是跟 x 差 2 的次方倍 ； 注意 < 的细节 , 举例 8  (i = 1 , 2, 4 ) , 若 <= 则有 i = 8 , tree[0] 的加入.
		tree[x] = max(tree[x] , tree[x - i]); // 注意是tree数组 , 有是定义域上的一点代表 a 数组的一个区间 , 用 lowbit , 往回推一定可以能覆盖到一开始 a[x] 修改为 y 的影响.
	}
}

区间查询

int ask(int x,int y){
	int ans = 0;
	while( y>=x ){
		ans = max(ans , a[y]) , y -= 1; //这里为什么要这样做?我要去除我这一点,在找我的子区间；
		for(;y-lowbit(y)>=x;）//我维护的子区间大于x , 我这个 x 才有用.
			ans = max(ans , tree[y]);
			y -= lowbit(y);
	}
	//等价于for(;y-lowbit(y)>=x;y-lowbit(y)) //判断->执行->减->判断....
	return ans;
}