Memory Efficient Segment Trees

Revision en1, by Bruteforceman, 2024-07-15 07:27:24

Segment trees are not as memory efficient as fenwick trees which often becomes the bottleneck of many problems. There has been attempts at reducing the space required to build a segment tree (e.g. iterative implementation takes $$$2N$$$ space instead of $$$4N$$$ space). But there's a very simple solution to this that can asymptotically improve the space complexity (sorry if this is already well-known).

When building the segment tree, we can simply stop the recursion when $$$r - l \leq \lg n$$$. This means the size of the tree is $$$O \left( \frac{n}{\lg n} \right)$$$ instead of $$$O(n)$$$.

Fortunately we can still answer queries (or perform updates) in $$$O(\lg n)$$$ time for most problems. For the internal nodes, we can simply collect the contribution of that node just like usual. For the leaf nodes with range $$$[l, r]$$$, we will have to scan through the original array in $$$a[l \cdots r]$$$ with a loop and calculate their contribution to the query. Since $$$r - l \leq \lg n$$$, the loop still takes $$$O(\lg n)$$$ time. Any range update/query visits only two leaf nodes, so the time required to process the leaf nodes are also $$$O(\lg n)$$$.

This trick may not be that useful if we need only one segment tree in our problem. However, many problems require building multiple segment trees. For example, one common pattern is to create a segment tree for each bit position. Applying this trick to such problems can reduce the space complexity from $$$O(n \lg n)$$$ to $$$O(n)$$$.

Tags segment tree, data structures, memory usage

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Bruteforceman 2024-07-15 08:23:08 89 Tiny change: 'O(n)$.\n\nExample Problem:\n- [E. XO' -> 'O(n)$.\n\n### Example Problem:\n\n- [E. XO'
en1 English Bruteforceman 2024-07-15 07:27:24 1489 Initial revision (published)