RMQ 算法

http://blog.csdn.net/niushuai666/article/details/6624672

通过学习这位神牛的文章初步认识 RMQ....

View Code

 1 #include <iostream>
 2 #include <cmath>
 3 #define maxn 10005
 4 using namespace std;
 5 int maxsum[maxn][20], minsum[maxn][20];
 6 
 7 void RMQ(int num)    //预处理->O(nlogn)  
 8 {
 9     int i, j;
10     for(j = 1; j < 20; ++j)
11       for(i = 1; i <= num; ++i)
12       if(i + (1 << j) -1 <= num)
13       {
14           maxsum[i][j] = max(maxsum[i][j-1], maxsum[i+(1 << j)][j-1]);
15           minsum[i][j] = min(minsum[i][j-1], minsum[i+(1 << j)][j-1]);
16         }
17 }
18 
19 int main()
20 {
21     int i, j, num, t, query;
22     cin >> t;
23     while(t--)
24     {
25         cin >> num >> query;
26         for(i = 0; i < num; i++)
27         {
28             cin >> maxsum[i][0];
29             minsum[i][0] = maxsum[i][0];
30         }
31         RMQ(num);
32         int start, end, maxl, minl;
33         while(query--) //o(1) 查询 
34         {
35             cin >> start >> end;
36             int k = (int)((log(end-start+1))/log(2.0));
37             maxl = max(maxsum[start][k], maxsum[end-(1 << k)+1][k]);
38             minl = min(minsum[start][k], minsum[end-(1 << k)+1][k]);
39             cout << maxl << minl << endl;
40         }
41     }
42     return 0;
43 }

讲解的ST() 算法.. 在敲代码的时候,想到这个算法预处理的时候消耗的时间会相对线段树等的时间长点, 但是在查询的时候就变得O(1).

本来是想是不是线段树的他都能处理呢?　我想是不可以的, 正是因为他的处理的时间略长, 如果说是边处理和边询问的话是不是就会变得时间上受不了.

那么它就是只是用于处理完所有的数据之后再查询的情况下, 如果操作和询问交叉的时候时间上会不能忍受.

自己现在的想法，也许想错。下次想到更多的再补充。