转载

【进阶——树状数组】区间求最值

上一篇讲的是区间求和，这一篇讲区间求最值。

首先， a[] 数组仍然是保存原始数据。但是 c[] 数组变了， c[i] 将会保存从 a[1] 到 a[i] 的最值。

初始化 c[] ：

当我们输入 a[i] 时， c[i] 需要需要向前依次枚举被 c[i] 所包含的 c[] 数组。比如，当 i == 8 时，需要向前依次枚举 c[7], c[6], c[4] ，取 a[8] 与这几个 c[] 中的最值保存在 c[8] 中。找到 c[] 的规律了没有？依次是 i-1, i-2, i-4...

1 void Init()  2 {  3     int  y;  4     memset(c, 0, sizeof(c));  5     for(int i = 1; i <= n; i++)  6     {  7         scanf("%d", &y);  8         a[i] = y;  9         c[i] = y; 10         for(int j = 1; j <lowbit(i); j <<= 1)           //需要比较的c[] 11             c[i] = c[i] > c[i-j] ? c[i] : c[i-j]; 12     } 13 }

可以看出，每输入一个 a[i] ，处理 c[i] 的时间复杂度为 log2(n) ，输入 n 个，初始化的时间复杂度就是 n*log2(n) 。

修改 c[] ：

我们改变了一个 a[i] ，那么就需要修改所有与 a[i] ，相关的 c[] 。修改每个的 c[] 的方法可以用上面初始化的方法，而需要修改的 c[] 可以用区间求和里的一段代码确定。

1 void Maxn(int x, int y)  2 {  3     a[x] = y;  4     for(int i = x; i <= n; i += lowbit(i))              //需要修改的c[]  5     {  6         c[i] = y;  7         for(int j = 1; j < lowbit(i); j <<= 1)          //修改时需要比较的c[]  8         {  9             c[i] = c[i] > c[i-j] ? c[i] : c[i-j]; 10         } 11     } 12 }

每次修改的时间复杂度近似为 log2(n)*log2(n) 。

查询：

查询从 a[i] 到 a[j] 之间的最值 (i <= j) 。我们不能直接查看 c[j] ，因为也许 c[j] 中包含的区间 [l, r] 中 l < i 或 l > i ， c[j] 不能恰好包含区间 [i, j] 。

因此，当 l < i 时，我们就取 a[j] 与当前已经取到的最值比较，如果 a[j] 满足取代条件，就用 a[j] 取代当前最值。

当 l >= i ，我们取 c[j] 与当前最值比较，如果 c[j] ，满足取代条件，就用 c[j] 取代当前最值。

当 l == i 时，比较结束。

1 void Query(int l, int r)  2 {  3     int ans = 0;  4     while(1)  5     {  6         ans = ans > a[r] ? ans : a[r];  7         if(r == l) break;  8         for(r -= 1; r-l >= lowbit(r); r -= lowbit(r))  9             ans = ans > c[r] ? ans : c[r]; 10     } 11     printf("%d/n", ans); 12 }

时间复杂度近似为 log2(n) 。

1 #include <cstdio>  2 #include <cmath>  3 #include <cstring>  4 #include <algorithm>  5 using namespace std;  6   7 const int N = 200010;  8   9 int a[N], c[N]; 10 int t, n, m; 11  12 int lowbit(int x) 13 { 14     return x&(-x); 15 } 16  17 void Maxn(int x, int y) 18 { 19     a[x] = y; 20     for(int i = x; i <= n; i += lowbit(i))              //需要修改的c[] 21     { 22         c[i] = y; 23         for(int j = 1; j < lowbit(i); j <<= 1)          //修改时需要比较的c[] 24         { 25             c[i] = c[i] > c[i-j] ? c[i] : c[i-j]; 26         } 27     } 28 } 29  30 void Init() 31 { 32     int  y; 33     memset(c, 0, sizeof(c)); 34     for(int i = 1; i <= n; i++) 35     { 36         scanf("%d", &y); 37         a[i] = y; 38         c[i] = y; 39         for(int j = 1; j <lowbit(i); j <<= 1)           //需要比较的c[] 40             c[i] = c[i] > c[i-j] ? c[i] : c[i-j]; 41     } 42 } 43  44 void Query(int l, int r) 45 { 46     int ans = 0; 47     while(1) 48     { 49         ans = ans > a[r] ? ans : a[r]; 50         if(r == l) break; 51         for(r -= 1; r-l >= lowbit(r); r -= lowbit(r)) 52             ans = ans > c[r] ? ans : c[r]; 53     } 54     printf("%d/n", ans); 55 } 56  57 void Work() 58 { 59     char s[2]; 60     int x, y; 61     for(int i = 1; i <= m; i++) 62     { 63         scanf("%s%d%d", s, &x, &y); 64         if(s[0] == 'U') Maxn(x, y); 65         else if(s[0] == 'Q') Query(x, y); 66     } 67 } 68  69 int main() 70 { 71     //freopen("test.in", "r", stdin); 72     while(~scanf("%d%d", &n, &m)) 73     { 74         Init(); 75         Work(); 76     } 77 }  mod

树状数组区间求和——

http://www.cnblogs.com/mypride/p/5001858.html

正文到此结束