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