董的博客 >> 算法之LCA与RMQ问题



董的博客 » 算法之LCA与RMQ问题

1、  概述 2、  RMQ算法 本节介绍了一种比较高效的在线算法(ST算法)解决这个问题。所谓在线算法,是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理,待信息充足以后便可以用较少的时间回答每个查询。ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。 首先是预处理,用动态规划(DP)解决。设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7,F[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。 F[1,2]=5,F[1,3]=8,F[2,0]=2,F[2,1]=4……从这里可以看出F[i,0]其实就等于A[i]。这样,DP的状态、初值都已经有了,剩下的就是状态转移方程。我们把F[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段(长度都为2^(j-1))。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i,j]就是这两段的最大值中的最大值。于是我们得到了动态规划方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。 然后是查询。取k=[log2(j-i+1)],则有:RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]}。 举例说明,要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。 算法伪代码: //初始化 INIT_RMQ //max[i][j]中存的是重j开始的2^i个数据中的最大值,最小值类似,num中存有数组的值 for i : 1 to n max[0][i] = num[i] for i : 1 to log(n)/log(2) for j : 1 to (n+1-2^i) max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)] //查询 RMQ(i,

Read full article from 董的博客 » 算法之LCA与RMQ问题


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts