Bukti Kompleksitas Waktu untuk implementasi Pohon Segmen dari masalah jumlah berkisar

10

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 .AO(logn)

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 ) .O(logn)4O(4logn)=O(logn)

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.

Arijit Choudhury
sumber
bangunan pohon segmen adalah O (n), kueri adalah O (log n) dan pembaruan adalah O (log N). Manfaatnya dari jumlah array adalah pada kompleksitas pembaruannya.
Nurlan

Jawaban:

11

2

Pertimbangkan ruas pohon yang diberikan di bawah ini.

Pohon Segmen

32logn2logn=Θ(logn)

Adijo
sumber