[树状数组求极值
[转载]树状数组求极值
(2012-08-28 11:43:07)
以往我们用树状数组一般只是求和，其实它还能用来求区间极值。
用d 表示原数组，t 表示线段树组。我们知道，t[i]表示的区间是[i-lowbit(i)+1, i]，类比线段树的操作，我们可以对树状数组做小小的改动，从而求区间极值。
对于区间[l,r]的询问操作：
⒈r表示的区间在[l,r]内，那么就取t[i]，并使r = r - lowbit(r)。
⒉r表示的区间不在[l,r]内，那么只取d[r]，并使r = r - 1。
迭代上述过程，取的各个值的最大值即为所求极值。
这样做的正确性显而易见，但是时间呢？为什么它能满足O(logN)的时间？
粗略地分析一下：对于情况⒈，理想情况下，r 自然能在logN 时间内到达l ，然而不理想时，有可能会进入情况⒉；
对于情况⒉，可以想象r 的二进制表示中，末尾有较多的0，当r' = r-1后，这些0就变成了1。于是进入了情况⒈。
情况⒈、情况⒉间的“往返”会不会有很多次呢？实际上，由于r 的二进制最多有logr+1位，这种“往返”最多只有O(logr)次，并且当“往返”次数多时，每种情况的迭代次数将会接近logr/2，于是时间就是O(logN)的了。
对于点w 的修改操作：
修改了d[w]的同时还要修改t[w]。因为t[w]的来源不只d[w]，还有众多子节点(w - 2^j)，j 满足2^j
例题：hdu1754裸题一道。
题意：修改一个值或者查询某段最大值，区间总大小2*10^5，操作次数5000。 分析：略。
附鄙陋程序：
#include
#include
#include
using namespace std;
const int maxn = 200010;
int n, m, d[maxn], maxi[maxn], l, r, lb[maxn];
char ch;
void insert(int w, int x)
{
for (d[w] = x; w
{
bool sma = (x
maxi[w] = x;
if (sma)
for (int j = 1; j
maxi[w] = max(maxi[w], maxi[w-j]);
}
}
int find(int l, int r)
{
for (int tmp = d[r]; ;)
{
tmp = max(tmp, d[r]);
if (l == r) return tmp;
for (r--; r - l >= lb[r]; r -= lb[r]) tmp = max(tmp, max(d[r], maxi[r])); }
}
int main()
{
for (int i = 1; i
for (n = -1, scanf("%d%d", &n, &m); n != -1; n = -1, scanf("%d%d", &n, &m)) {
for (int i = 1; i
{
scanf("%d", &l);
insert(i, l);
}
for (int i = 1; i
{
for (ch = '=', scanf("%c", &ch); ch != 'Q' && ch != 'U'; scanf("%c", &ch));
scanf("%d%d", &l, &r);
if (ch == 'Q') printf("%dn", find(l, r));
else insert(l, r);
}
}
return 0;
}