Platzbedarf für den Segmentbaum ⇐ C++

[Anonymous]

Ich habe, wie in diesem Artikel auf HackerEarth erläutert, herausgefunden, dass Segmentbäume mithilfe von Arrays implementiert werden können, bei denen sich untergeordnete Elemente eines Knotens, der am Array-Index n positioniert ist, an den Indizes 2n und 2n+1 befinden.

Außerdem heißt es, dass ich zum Speichern von n Elementen in meinem Segmentbaum 2n+1 benötige Knoten.

Als ich kürzlich einige Probleme im Zusammenhang mit Segmentbäumen gelöst habe, gab mein Code manchmal einen Laufzeitfehler aus, der behoben wurde, als ich die Array-Größe zum Speichern des Segmentbaums auf 4 x (Größe des im Segmentbaum zu speichernden Arrays) änderte. Wie kann ich sicher sein, dass ein Segmentbaum tatsächlich ein Array der Größe 4n für n Elemente erfordert?