Bukti Kompleksitas Waktu untuk implementasi Pohon Segmen dari masalah jumlah berkisar

Saya mengerti bahwa pohon segmen dapat digunakan untuk menemukan jumlah sub array . Dan ini dapat dilakukan dalam waktu O ( log n ) sesuai dengan tutorial di sini .$A$$\mathcal{O}(\log n)$

Namun saya tidak dapat membuktikan bahwa waktu query memang . Tautan ini (dan banyak lainnya) mengatakan bahwa kita dapat membuktikan bahwa pada setiap level, jumlah maksimum node yang diproses adalah 4 dan jadi O ( 4 log n ) = O ( log n ) .$\mathcal{O}(\log n)$$4$$\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$

Tetapi bagaimana kita membuktikan ini, mungkin dengan kontradiksi?

Dan jika demikian, jika kita akan menggunakan pohon segmen untuk jumlah array dimensi yang lebih tinggi, bagaimana buktinya diperpanjang?

Sebagai contoh, saya dapat memikirkan menemukan jumlah sub matriks dengan membagi matriks asli menjadi 4 kuadran (mirip dengan separuh interval dalam array linier) membangun pohon segmen kuadran tetapi bukti menghindari saya.

$2$

Pertimbangkan ruas pohon yang diberikan di bawah ini.

$3$$2$$\log{n}$$\boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)}$