Segment tree solution is wrong. It's assuming the segment tree is a complete binary tree. but it's not. A simple test case can easily invalidate the wrong solution :
I think O(1) space is enough for this problem :
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.