RMQ Tarjan的Sparse-Table算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了RMQ Tarjan的Sparse-Table算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含834字，纯文字阅读大概需要2分钟。

内容图文

参考博客：https://www.cnblogs.com/wenzhixin/p/9714760.html

预处理时间复杂度是O(nlogn),代码如下：

 1 void init(const vector<int>& A) {
 2     int n = A.size();
 3     for(int i = 0; i < n; i++) {
 4         d[i][0] = A[i];//以i开头，长度为1的最小值是A[i] 
 5     }
 6     
 7     for(int j = 1; (1 << j) <= n; j++) {//再区间范围内枚举次方 
 8         for(int i = 0; i + (1 << j) - 1 < n; i++) {//枚举每一个开头，直到没有长度为2的j的区间 
 9             d[i][j] = min(d[i][j - 1], d[i + (1 << j) - 1][j - 1]);
10         }
11     }
12 }

查询是常数复杂度，这是RMQ的一大优点，相对于线段树的O(logn)复杂度有很大改进。查询的时候先给出最大的k s.t. 2^k<=R-L+1。代码如下：

1 int query(int L, int R) {
2      int k = 0;
3      while((1 << (k + 1)) <= R - L + 1) k++;//若2的k+1次方<= R - L + 1,则k还可以加1 
4     return min(d[L][k], d[R - (1 << k) + 1][k]);
5  } 

 

内容总结

以上是互联网集市为您收集整理的RMQ Tarjan的Sparse-Table算法全部内容，希望文章能够帮你解决RMQ Tarjan的Sparse-Table算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---