algorithmtreegraph-algorithminterval-treesegment-tree

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


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

Please do not just give definitions.


Solution

  • All these data structures are used for solving different problems:

    Performance / Space consumption for one dimension:

    (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:

    Higher dimensions (d>1):