What is the proof or explanation behind the fact that at most 4 nodes per level are visited in a segment tree?
On each level except the root one, at most two adjacent segments can be visited. Because if more were to be visited, some to of them would be united into one segment on an upper level (that node would be visited and its sons wouldn't, because its segment would fit). Than, there can be at most 2 groups of non-adjacent segments, so we get 2 * 2 is 4. There can be at most 2 groups because we can get a segment in the middle and than 2 additions to its sides, and than no more. After that the segments to the right/left would only need other lower-level segments to the right/left respectively.
I drew it a little bit so you could understand it better. The link to the seg tree image
