I’m doing the Monkey and Apple-Trees problem right now from the Sparse Segment Tree tutorials, but I can’t figure out how much memory my segment tree needs. The tutorial says that we only need O(Q(log(n))) nodes, and in this problem Q = 1e5 and n = 1e9, so memory complexity should be O(3e6). However, if I make my segment tree this size, I get an error from the memory being too small.
In the solution the memory used was 123456 * 64, but this seems like an arbitrary number to me and it would be nice to have a way to calculate how much memory a sparse segtree actually needs so that in future contests I’m not just guessing.
Can anyone help?
Link to tutorial: https://usaco.guide/plat/sparse-seg?lang=cpp
Link to problem: View problem - Monkey and Apple-trees (IZhO12_apple) :: oj.uz