树状数组维护区间最值

发布于 2023-03-10  443 次阅读


说起区间最值,容易想到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;
}