Range sum query - efisiensi representasi pohon
Saya membaca tentang kemungkinan solusi untuk masalah yang terkenal:
Diberikan array
Adengan panjangNmembuat struktur yang memungkinkan
- Menjawab berapa jumlahnya $\sum_{k=i}^{j} A[k]$
- Memperbarui $A[k]$
Saya telah melihat sebagian besar solusi menggunakan pohon indeks biner tetapi penasaran apakah mungkin hanya menggunakan pohon biasa yang dibangun menggunakan kualitas yang sama.
Jadi diberikan $A = [5, 4, 7, 9, 1]$
Saya mencoba membangun pohon dengan membuat simpul pohon untuk setiap nilai yang memiliki awal dan akhir (yang hanya indeks pada awalnya.
Untuk membangun pohon, saya mendorong semua simpul awal ke dalam antrian $Q$
while not Q.empty():
next <- []
for i in range(Q.size()):
f <- Q.front()
Q.pop()
if Q.empty():
if marker:
parent <- make_parent(f, marker)
next.push(parent)
else:
marker <- f
else:
f2 <- Q.front()
Q.pop()
parent <- make_parent(f, marker)
next.push(parent)
for n in next:
Q.push(n)
Setelah ujung ini penanda akan menahan akarnya
(Saya memiliki kode c ++ tetapi saya mencoba memberikan sesuatu yang lebih abstrak dan sederhana)
dan untuk mendapatkan jumlah rentang saya melakukan hal berikut (dengan asumsi saya memiliki array Nodes yang menampung semua daun) dan bahwa kueri dimulai dengan akar pohon yang kami buat di atas
sumRangeNode(int i, int j, Node* n)
if i == j
return Nodes[i]
if n == null
return 0
if j < n->start || i > n->end
return 0;
if i <= n->start && j >= n->end
return n->val
return sumRangeNode(i, j, n->left) + sumRangeNode(i, j, n->right)
Pertanyaannya adalah apakah masih ada $\log(N)$ kompleksitas, saya telah mencoba untuk menjelaskannya tetapi berjuang dengan:
- Fakta bahwa saya mungkin membangun pohon dengan "orang yang tersesat" seperti itu $1$ dalam contoh
- Fakta bahwa saya menjelajahi kanan dan kiri secara rekursif . Intuisi memberi tahu saya bahwa karena ada "cukup" kasus di mana penurunan dihentikan tidak masalah tetapi tidak dapat menemukan cara untuk memformalkan / membuktikannya.
Jawaban
Pendekatan ini berhasil. Sebuah "Binary-Indexed-Tree" hanyalah pohon biner seimbang implisit dengan beberapa "kompresi" tambahan. Lihat jawaban ini untuk detail tentang bagaimana dan mengapa ini dilakukan, tetapi pada dasarnya tujuannya hanya untuk berjalan dalam siklus yang lebih sedikit.
Pendekatan Anda bekerja dengan baik secara asimtotik dan mungkin bahkan akan bekerja dengan baik dalam praktiknya.
Pertama, apakah pohon yang dihasilkan oleh antrian Anda selalu dijamin "pendek"? Jawabannya iya. Cara termudah untuk melihatnya adalah dengan memperhatikan bahwa penggunaan antrian Anda secara alami menjadi "masa", di mana setiap zaman membangun kira-kira satu tingkat pohon.
Pertama, sebagai penyederhanaan, jangan repot-repot melacaknya markedsecara terpisah dari yang lain. Sebagai gantinya, ulangi loop sampai Qhanya memiliki satu elemen, dan kemudian biarkan itu menjadi root Anda. Ini menyederhanakan status Anda dan membuatnya lebih mudah untuk diikuti.
while q.size() > 1:
next = []
while q.size() > 0:
a := q.pop()
if q.empty():
next.push(a)
else:
b := q.pop()
next.push(make_parent(a, b))
for v in next:
q.push(v)
root := q.pop()
Jika antrian berisi semua $n$ sebelum iterasi, lalu setelah itu akan berisi salah satunya $\lfloor n / 2 \rfloor$ atau $\lfloor n / 2 \rfloor + 1$ node tergantung pada apakah $n$ adalah genap atau ganjil.
Selain itu, tinggi maksimum node dalam larik akan meningkat paling banyak satu, karena setiap node hanya dipasangkan dengan satu sama lain (analisis yang cermat akan menunjukkan bahwa itu selalu meningkat tepat satu, tetapi kami sebenarnya tidak peduli).
Pengamatan pertama memberi tahu kita bahwa loop akan berjalan $O(\log n)$iterasi. Oleh karena itu, yang kedua memberi tahu kita bahwa pohon yang dihasilkan akan memiliki tinggi paling banyak$O(\log n)$ karena ketinggian pohon dalam antrian meningkat paling banyak 1 setiap iterasi.
Jadi pohon itu mungkin tidak "seimbang" secara sempurna, tetapi tingginya masih dibatasi $O(\log n)$ dan dengan demikian setiap operasi yang berjalan dalam waktu yang dibatasi oleh ketinggian pohon akan berjalan $O(\log n)$ waktu.
Fakta bahwa saya menjelajahi kanan dan kiri secara rekursif. Intuisi memberi tahu saya bahwa karena ada "cukup" kasus di mana penurunan dihentikan tidak masalah tetapi tidak dapat menemukan cara untuk memformalkan / membuktikannya.
Ini sebenarnya mudah. Misalkan pohon Anda memiliki node di beberapa tingkat yang terlihat di bawah ini, di mana [--...--]menunjukkan kisaran nilai dalam larik asli yang diwakili oleh node tersebut.
Kueri yang sesuai akan digambar dengan (...). Ada (secara umum) hanya beberapa jenis yang perlu dikhawatirkan:
[---------------45-----------------]
[------------30----------][---15---]
(- - Q1 - -)
(- - Q2 - -)
(- - Q3 - -)
(- - - - - Q4 - - - -)
(- - - - - - - - Q5 - - - - - - - - - - -)
Perhatikan bahwa Q2 dan Q4 memiliki bentuk simetris yang saya hilangkan.
- Q1 hanya melintasi bagian kiri
- Q2 hanya melintasi bagian kiri
- Q3 melintasi kedua bagian
- Q4 melintasi kedua bagian
- P5 mencakup seluruh rentang, sehingga tidak akan melintasi juga
Jadi kita hanya perlu menganalisis Q3 dan Q4.
Q4 benar-benar menutupi setengah bagian kanan, sehingga "traversal" dijamin konstan. Jadi hanya separuh kiri yang melintasi ke kedalaman yang tidak konstan.
Jadi, satu-satunya kasus yang "menarik" adalah kueri tipe-Q3, yang hanya melintasi sebagian rentang anak kiri dan rentang anak kanan.
Perhatikan bahwa kueri tipe-Q3 meluas ke tepi kiri anak kanan, dan ke tepi kanan anak kiri.
Ini berarti bahwa di subpohon, tidak akan ada kueri tipe-Q3, yang tidak dapat diperluas ke salah satu tepi. Semua kueri akan benar-benar kehilangan setiap node, menutupinya sepenuhnya, atau melampaui batas.
Jadi akan ada paling banyak satu kueri tipe-Q3 di seluruh hierarki (perhatikan bahwa tipe Q5 juga memeriksa kedua turunan, tetapi mereka "cepat").
Karena hanya ada satu dari mereka, Anda pada dasarnya dapat mengabaikannya dalam analisis - paling banyak $O(\log n) + O(\log n) = O(\log n)$ node akan dikunjungi.