树状数组维护区间最值

说起区间最值，容易想到ST表（动态规划写法），但是这种方法不能动态维护，只能维护一个固定的数组。再容易想到线段树，但是线段树的常数极大，每次写线段树都心惊胆战，就怕t了。

这篇文章介绍一下树状数组来维护区间最值。

回顾一下树状数组

说起树状数组，容易想到树状数组可以动态维护区间和，可以实现区间修改和区间查询。

它大概长这样：

对于一个节点k，他的管辖区间为[k - lowbit(k) + 1, k]，其本身作为右端点。

对于lowbit的解释：

lowbit(x) = x & -x

其数学含义是取出数字x的二进制表示中的从右往左第一个1，然后截断，例如lowbit(1011000)=(1000)

树状数组维护区间最值

树状数组维护的区间最值仅支持单点修改和区间查询。

值得注意的是，维护一个最值树状数组需要同时维护两个数组，分别是t（树状数组）和a（原数组）。

单点修改：复杂度O((logn)^2)

void update(int k, int x)//维护区间最大值，最小值只需要改max为min即可
{
	a[k] = x;
	while(k < maxn)
	{
		t[k] = x;
		for(int i = 1;i < lowbit(k); i <<= 1)
		{
			t[k] = max(t[k], t[k - i]);
		}
		k += lowbit(k);
	}
}

区间查询：复杂度O((logn)^2)

int queMax(int l, int r)
{
	int res = a[r];
	while(r >= l)
	{
		for(;r - lowbit(r) >= l; r -= lowbit(r))
		{
			res = max(res, t[r]);
		}
		res = max(res, a[r --]);
	}
	return res;
}