Graph Theory37 sections · 1633 units
Open in Course

Space Complexity

(Memory usage)

Euler tour with entry-exit times uses nn positions for entry times. Each node occupies one entry position. Segment tree on this array uses O(n)O(n) space (the tree has 4n4n nodes but that is still O(n)O(n)).

BIT uses O(n)O(n) space directly. Total memory: O(n)O(n) for the tree structure, O(n)O(n) for flattened array, O(n)O(n) for segment tree or BIT. All linear. For n=200,000n = 200,000, you need around 33 to 44 megabytes total, well within typical memory limits.