blocks|key|2798872|text|所有这些数据结构都用于解决不同的问题：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2798873|2798874|Segment树存储间隔，并针对“这些间隔中的哪些包含给定点”进行了优化。queries.|unordered-list-item|offset|length|style|BOLD|2798875|Interval树也存储了间隔，但针对“这些间隔中的哪些与给定的间隔重叠”查询进行了优化。它也可以用于点查询-类似于段树。|2798876|Range树存储点数，并针对“哪些点落在给定间隔内”进行了优化。queries.|2798877|Binary索引树存储每个索引的项数，并针对“索引m和n之间有多少项”查询进行了优化。|2798878|2798879|一个维度的性能/空间消耗：|2798880|2798881|Segment树-+O(k%2Blogn)预处理时间，O(k%2Blogn)查询时间，O(k%2Blogn)+|2798882|Segment树-O(k%2Blogn)预处理时间，O(logn)查询时间，O(n)+space|2798883|Range树-O(k%2Blogn)预处理时间，O(k%2Blogn)查询时间，O(n)+space|2798884|Range索引树-O(k%2Blogn)预处理时间，O(+logn)查询时间，O(n)+|2798885|2798886|2798887|(k是报告结果的数量)。|2798888|所有数据结构都可以是动态的，因为使用场景包括数据更改和查询：|2798889|2798890|Segment树计数-间隔可以在O(logn)时间内添加/删除(请参阅here)|2798891|Interval树-间隔可以在O(logn)时间内添加/删除)|2798892|Segment树-新点可以在O(logn)时间内添加/删除(请参阅索引树-每个索引的项数可以在O(logn)时间内增加|2798893|2798894|2798895|更高维度(d>1)：|2798896|2798897|Segment树-+O(n(+logn)+%5Ed)预处理时间，O(k%2B(+logn)+%5Ed)查询时间，O(n(logn)%5E(d-1))+space|2798898|Range树-+O(n+Logn)预处理时间，O(k%2B(logn)%5Ed)查询时间，O(n+Logn)space|2798899|Range树k%2B-+O(n(logn)%5Ed)预处理时间，O(k%2B(logn)%5Ed)查询时间，O(n(Logn)%5E(d-1)+space|2798900|Binary索引树-+O(n(logn)%5Ed)预处理时间，O((logn)%5Ed)查询时间，O(n(logn)%5Ed)+space|2798901|Binary|2798902|2798903|entityMap|0|LINK|mutability|MUTABLE|url|http://3glab.cs.nthu.edu.tw/~spoon/courses/CS631100/Lecture05_handout.pdf^0|0|0|0|8|0|0|9|0|0|14|0|0|17|0|0|0|D|0|0|0|1D|1|0|1A|1|0|1A|1|0|16|1|0|0|0|C|0|0|U|0|0|0|14|Z|4|0|0|0|V|1|0|10|1|0|0|0|0|0|8|0|0|6|0|0|1V|0|0|1R|0|0|6|0|0^^$0|@$1|2|3|4|5|6|7|22|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|23|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|24|8|@$F|25|G|26|H|I]]|9|@]|A|$]]|$1|J|3|K|5|E|7|27|8|@$F|28|G|29|H|I]]|9|@]|A|$]]|$1|L|3|M|5|E|7|2A|8|@$F|2B|G|2C|H|I]]|9|@]|A|$]]|$1|N|3|O|5|E|7|2D|8|@$F|2E|G|2F|H|I]]|9|@]|A|$]]|$1|P|3|-4|5|6|7|2G|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|2H|8|@$F|2I|G|2J|H|I]]|9|@]|A|$]]|$1|S|3|-4|5|6|7|2K|8|@]|9|@]|A|$]]|$1|T|3|U|5|E|7|2L|8|@$F|2M|G|2N|H|I]]|9|@]|A|$]]|$1|V|3|W|5|E|7|2O|8|@$F|2P|G|2Q|H|I]]|9|@]|A|$]]|$1|X|3|Y|5|E|7|2R|8|@$F|2S|G|2T|H|I]]|9|@]|A|$]]|$1|Z|3|10|5|E|7|2U|8|@$F|2V|G|2W|H|I]]|9|@]|A|$]]|$1|11|3|-4|5|6|7|2X|8|@]|9|@]|A|$]]|$1|12|3|-4|5|6|7|2Y|8|@]|9|@]|A|$]]|$1|13|3|14|5|6|7|2Z|8|@$F|30|G|31|H|I]]|9|@]|A|$]]|$1|15|3|16|5|6|7|32|8|@$F|33|G|34|H|I]]|9|@]|A|$]]|$1|17|3|-4|5|6|7|35|8|@]|9|@]|A|$]]|$1|18|3|19|5|E|7|36|8|@$F|37|G|38|H|I]]|9|@$F|39|G|3A|1|3B]]|A|$]]|$1|1A|3|1B|5|E|7|3C|8|@$F|3D|G|3E|H|I]]|9|@]|A|$]]|$1|1C|3|1D|5|E|7|3F|8|@$F|3G|G|3H|H|I]]|9|@]|A|$]]|$1|1E|3|-4|5|6|7|3I|8|@]|9|@]|A|$]]|$1|1F|3|-4|5|6|7|3J|8|@]|9|@]|A|$]]|$1|1G|3|1H|5|6|7|3K|8|@]|9|@]|A|$]]|$1|1I|3|-4|5|6|7|3L|8|@]|9|@]|A|$]]|$1|1J|3|1K|5|E|7|3M|8|@$F|3N|G|3O|H|I]]|9|@]|A|$]]|$1|1L|3|1M|5|E|7|3P|8|@$F|3Q|G|3R|H|I]]|9|@]|A|$]]|$1|1N|3|1O|5|E|7|3S|8|@$F|3T|G|3U|H|I]]|9|@]|A|$]]|$1|1P|3|1Q|5|E|7|3V|8|@$F|3W|G|3X|H|I]]|9|@]|A|$]]|$1|1R|3|1S|5|E|7|3Y|8|@$F|3Z|G|40|H|I]]|9|@]|A|$]]|$1|1T|3|-4|5|6|7|41|8|@]|9|@]|A|$]]|$1|1U|3|-4|5|6|7|42|8|@]|9|@]|A|$]]]|1V|$1W|$5|1X|1Y|1Z|A|$20|21]]]]

All these data structures are used for solving different problems:

<ul>
<li>Segment tree stores intervals, and optimized for "which of these intervals contains a given point" queries.</li>
<li>Interval tree stores intervals as well, but optimized for "which of these intervals overlap with a given interval" queries. It can also be used for point queries - similar to segment tree. </li>
<li>Range tree stores points, and optimized for "which points fall within a given interval" queries.</li>
<li>Binary indexed tree stores items-count per index, and optimized for "how many items are there between index m and n" queries.</li>
</ul>

Performance / Space consumption for one dimension:

<ul>
<li>Segment tree - O(n logn) preprocessing time, O(k+logn) query time, O(n logn) space</li>
<li>Interval tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space</li>
<li>Range tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space</li>
<li>Binary Indexed tree - O(n logn) preprocessing time, O(logn) query time, O(n) space</li>
</ul>

(k is the number of reported results).

All data structures can be dynamic, in the sense that the usage scenario includes both data changes and queries:

<ul>
<li>Segment tree - interval can be added/deleted in O(logn) time (see <a href="http://3glab.cs.nthu.edu.tw/~spoon/courses/CS631100/Lecture05_handout.pdf">here</a>)</li>
<li>Interval tree - interval can be added/deleted in O(logn) time</li>
<li>Range tree - new points can be added/deleted in O(logn) time (see <a href="http://www.cs.unb.ca/tech-reports/documents/TR95_100.pdf">here</a>)</li>
<li>Binary Indexed tree - the items-count per index can be increased in O(logn) time</li>
</ul>

Higher dimensions (d>1):

<ul>
<li>Segment tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1)) space</li>
<li>Interval tree - O(n logn) preprocessing time, O(k+(logn)^d) query time, O(n logn) space</li>
<li>Range tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1))) space</li>
<li>Binary Indexed tree - O(n(logn)^d) preprocessing time, O((logn)^d) query time, O(n(logn)^d) space</li>
</ul>

blocks|key|184336|text|可以改进分段树和二进制索引树的预处理和空间的界限：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|184337|184338|段树可以存储在2n空间中，随后可以使用动态编程在2n+=+O(n)中构建，如果您放弃在任何任意点添加间隔：https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6|unordered-list-item|offset|length|style|CODE|184339|BIT可以在O(log(n))中构建，请参阅以下答案：Is+it+possible+to+build+a+Fenwick+tree+in+O(n)?|184340|BIT还支持在2n+=+O(n)+time|184341|中作为操作追加到末尾|184342|entityMap|0|LINK|mutability|MUTABLE|url|https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6|1|https://stackoverflow.com/questions/31068521/is-it-possible-to-build-a-fenwick-tree-in-on?rq=1^0|0|0|7|2|O|9|1H|1X|0|0|6|9|R|1B|1|0|7|9|0|0^^$0|@$1|2|3|4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|10|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|11|8|@$F|12|G|13|H|I]|$F|14|G|15|H|I]]|9|@$F|16|G|17|1|18]]|A|$]]|$1|J|3|K|5|E|7|19|8|@$F|1A|G|1B|H|I]]|9|@$F|1C|G|1D|1|1E]]|A|$]]|$1|L|3|M|5|E|7|1F|8|@$F|1G|G|1H|H|I]]|9|@]|A|$]]|$1|N|3|O|5|6|7|1I|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|1J|8|@]|9|@]|A|$]]]|Q|$R|$5|S|T|U|A|$V|W]]|X|$5|S|T|U|A|$V|Y]]]]

The bounds for preprocessing and space for segment trees and binary indexed trees can be improved:
<ul>
<li>Segment trees can be stored in <code>2n</code> space and subsequently built in <code>2n = O(n)</code> using dynamic programming, if you forgo adding intervals at any arbitrary point: <a href="https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6" rel="nofollow noreferrer">https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6</a></li>
<li>BIT can be built in <code>n</code>, see this answer: <a href="https://stackoverflow.com/questions/31068521/is-it-possible-to-build-a-fenwick-tree-in-on?rq=1">Is it possible to build a Fenwick tree in O(n)?</a></li>
<li>BIT also supports append to end as an operation in <code>O(log(n))</code> time</li>
</ul>

What are differences between segment trees, interval trees, binary indexed trees and range trees in terms of:

<ul>
<li>Key idea/definition </li>
<li>Applications </li>
<li>Performance/order in higher dimensions/space consumption</li>
</ul>

Please do not just give definitions.

What are the differences between segment trees, interval trees, binary indexed trees and range trees?

数据结构

段树、区间树、二进制索引树和范围树在以下方面有何不同：Key idea/definition Applications in higher dimensions/空间消耗/请不要只给出定义。

问段树、区间树、二进制索引树和范围树有什么不同？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问段树、区间树、二进制索引树和范围树有什么不同？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问段树、区间树、二进制索引树和范围树有什么不同？
EN