QFire的专栏通过本文主要向大家介绍了区间算法,置信区间算法,区间调度算法,区间优化算法,区间树等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
区间树常用于在一维数组的特定区间对查询进行快速回复。区间树的最简单的应用就是求区间最小值的问题。
假设对某个数组A的子区间进行多次求最小元素的运算。例如，A={1, 2, 1, 2, 3, 1, 2, 3, 4}，那么区间[2, 4]的最小值是1。需要O(n)
区间树的基本思路是，生成表示给定数组各区间的二叉树。此时，区间树的根节点总是表示整个空间[0, n-1]。需要O(lgn)