Memory efficent Persistent Segment Trees

Revision en1, by ricardogg, 2019-07-19 13:58:59

Hello everyone,

Recently I was trying to implement a working persistent segment tree, and I managed to solve couple problems with it.

However for one problem I needed to implement persistent segment tree with $$$100000$$$ values in the leafs, and two long long values in each node while the memory limit is only $$$64$$$ megabytes. Firstly I created version that works with pointers, however later I replaced the pointers with integers representing each node, but neither of those version is not working in the memory limit.

What is the best way to implement such tree, are there any tricks to reduce the memory usage?

Tags #segment tree, #persistence, #implementation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ricardogg 2019-07-19 13:58:59 660 Initial revision (published)