bas*_*sav 3 c++ stl range-tree
我有一个要求,我必须根据一些属性值更新图形前端的颜色.属性值有不同的范围....比如-30到-45,-60到-80等等....那么,我需要一个数据结构,我可以存储这些范围(预填充它们)....当我确定这一点时,我想知道这一点落在O(1)时间或O的范围内(logN)时间....所以,我的查询将由一个点组成,输出应该是包含该点的唯一范围...
我在范围树和段树之间感到困惑....我想在c ++ stl map之上构建树.
你需要的是间隔树.http://en.wikipedia.org/wiki/Interval_tree.遗憾的是,您无法使用std::set<>O(log N)插入,删除和查询,因为树节点需要包含其他数据.你可以在这里阅读它们http://syedwaqarahmad.webs.com/documents/t.cormen -_introduction_to_algorithms_3rd_edition.pdf
第14.3章.
相反,你可以使用提升.它有间隔容器库.
http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html