Skip to content

Comment on Ask HN: Fast data structures for disjoint intervals?parent

Comments

Does the range query aggregate the elements in range? If the aggregation operation forms a group (follows associativity law, has inverse) you can use prefix sum data structures like Fenwick tree.

If it doesn't have inverse so that you cannot subtract prefix sum, sparse table can be used.

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.