algoritma untuk masalah paritas awalan

Masalah paritas awalan dapat didefinisikan sebagai berikut. Anda diberi string dengan panjang dan pada awalnya setiap karakter adalah . Maka Anda ingin membangun struktur data yang dapat mendukung pembaruan seperti berikut ini.$S$$n$$0$

1. Untuk yang diberikan mengubah menjadi atau$i$$S[i]$$0$$1$
2. untuk diberikan menemukan paritas .$i$$S[1]+S[2]+...+S[i]$

Dari atas kepala saya, ada solusi yang dapat mendukung jenis pertanyaan ini dalam waktu , sementara hanya menggunakan ruang linear dan waktu praproses linear untuk membangun struktur data. Idenya adalah untuk membangun pohon pencarian biner lengkap di atas string di mana daun sesuai dengan karakter individu dan di setiap simpul internal kita menyimpan jumlah semua karakter yang merupakan daun di sub pohon yang ditentukan oleh simpul itu. Dengan cara ini, kami dapat dengan mudah mendukung kedua pembaruan dalam waktu .$O(\log n)$$S$$O(\log n)$

Namun, saya menemukan makalah yang membuktikan batas bawah untuk masalah ini, menyatakan bahwa Anda tidak dapat melakukan lebih baik daripada untuk pembaruan, dan saya juga menemukan kertas berikut http://link.springer.com/chapter/10.1007%2F3-540-51542-9_5 , dan tautan langsung ke pdf , memberikan algoritme yang mencapai batas itu, sehingga menjadi optimal.$O(\frac{\log n}{\log \log n})$

Saya ingin memahami algoritme ini namun penjelasannya seperti 1 halaman, dan banyak detail yang hilang.

Jadi saya bertanya-tanya apakah ada sumber lain pada masalah ini, karena saya merasa sangat sulit untuk menemukan, atau apakah ini satu-satunya sumber yang tersedia?

Terima kasih sebelumnya

Saya membaca cepat kertas yang Anda tautkan. Berdasarkan ide yang diberikan dalam makalah itu, berikut adalah struktur data sederhana yang memperoleh$O(\frac{\log n}{\log\log n})$ terikat waktu pada setiap operasi.

Anda menyebutkan dalam pertanyaan Anda bahwa Anda dapat menggunakan pohon yang seimbang dan ditambah untuk mempercepat ini. Secara khusus, jika Anda memiliki pohon biner dan menambah setiap node dengan paritas subtree kirinya, maka Anda dapat melakukan pembaruan dan pencarian dalam waktu$O(\log n)$setiap. Itu cepat, tetapi tidak cukup cepat.

Sekarang, pertimbangkan generalisasi ide Anda berikut ini. Misalkan alih-alih menggunakan pohon biner, kami menggunakan pohon multiway dengan faktor percabangan$k$. Kami menambah setiap kunci di setiap node dengan paritas dari semua subtree yang mendahuluinya (ini menggeneralisasi ide untuk menyimpan paritas subtree kiri). Sekarang, mari kita pikirkan tentang bagaimana kita melakukan pencarian atau pembaruan di pohon ini. Untuk melakukan pencarian, kami menggunakan versi yang sedikit dimodifikasi dari algoritma pencarian pohon biner dari sebelumnya: berjalan dari atas pohon ke bawah, pada setiap langkah mengumpulkan paritas subtree murni di sebelah kiri setiap node. Ketinggian pohon dalam hal ini akan menjadi$O(\log_k n)$ dan kami lakukan $O(1)$ bekerja per node, jadi biaya melakukan pencarian akan $O(\log_k n)$.

Namun, dengan pengaturan ini, biaya melakukan pembaruan meningkat. Secara khusus, jika kita mengubah paritas elemen, kita perlu berjalan dari bawah pohon ke atas, mengubah paritas yang disimpan dari setiap kunci di setiap node di jalan menuju ke atas. Ada$k$ kunci per node dan $O(\log_k n)$ node pada jalur ke atas dari daun, sehingga biaya melakukan operasi seperti ini akan menjadi $O(k \log_k n) = O(\frac{k}{\log k} \log n)$, yang terlalu lambat. Jika kita entah bagaimana bisa menghilangkan ini ekstra$k$ istilahnya, maka kita akan berada dalam bisnis.

Wawasan yang dimiliki makalah ini adalah sebagai berikut. Jika Anda memikirkan masalah awal kami, kami memiliki berbagai ukuran$n$dan ingin dapat menghitung paritas awalan. Kami sekarang memiliki$k$-ary tree di mana, di setiap node, kita harus mampu menyelesaikan masalah paritas awalan pada array ukuran $k$masing-masing, karena setiap simpul menyimpan informasi tentang lapisan di bawahnya. Dalam struktur data di atas, kami memecahkan masalah paritas awalan di setiap node dengan hanya menyimpan array paritas awalan, yang berarti bahwa jika kita perlu melakukan pembaruan, biayanya adalah$O(k)$. Wawasan makalah ini adalah bahwa dengan menggunakan struktur data yang lebih pintar di setiap node, Anda dapat melakukan pembaruan ini secara signifikan lebih efisien.

Secara khusus, makalah ini membuat wawasan berikut. Mari kita anggap itu$k$adalah "kecil," untuk beberapa definisi kecil yang akan kami pilih nanti. Jika Anda ingin menyelesaikan masalah paritas awalan pada berbagai ukuran$k$, maka hanya ada $2^k$ mungkin sedikit berbeda panjang array $k$. Selain itu, hanya ada$k$ kemungkinan permintaan pencarian yang bisa Anda buat pada bit array ukuran $k$. Akibatnya, jumlah kemungkinan kombinasi array dan kueri adalah$k 2^k$. Jika kita memilih$k$untuk menjadi cukup kecil, kita dapat membuat jumlah ini sangat kecil sehingga menjadi layak untuk melakukan prakiraan hasil dari setiap kemungkinan array dan setiap kemungkinan query. Jika kami melakukan itu, maka kami dapat memperbarui struktur data kami sebagai berikut. Di setiap node$k$pohon jalan, daripada memiliki setiap kunci menyimpan paritas subtree kirinya, kami malah menyimpan array $k$bit, satu untuk setiap kunci di simpul. Ketika kita ingin menemukan paritas semua node di sebelah kiri$i$th anak, kita hanya melakukan pencarian di tabel yang diindeks oleh mereka $k$ bit (diperlakukan sebagai bilangan bulat) dan indeks $i$. Asalkan kita dapat menghitung tabel ini dengan cukup cepat, ini berarti melakukan permintaan paritas awalan masih akan memakan waktu$O(\log_k n)$, tetapi sekarang pembaruan membutuhkan waktu $O(\log_k n)$ juga karena biaya permintaan paritas awalan pada node yang diberikan akan $O(1)$.

Para penulis makalah memperhatikan bahwa jika Anda memilih $k = \frac{\lg n}{2}$, maka jumlah kueri yang mungkin bisa dibuat adalah $\frac{\lg n}{2} 2^{\frac{\lg n}{2}} = \frac{\lg n}{2} \sqrt{n} = o(n)$. Selain itu, biaya untuk melakukan operasi apa pun pada pohon yang dihasilkan akan menjadi$O(\log_k n) = O(\frac{\log n}{\log \frac{\lg n}{2}}) = O(\frac{\log n}{\log \log n})$. Tangkapannya adalah yang sekarang perlu Anda lakukan$o(n)$precomputation pada awal pengaturan struktur data. Para penulis memberikan cara untuk mengamortisasi biaya ini dengan menggunakan struktur data yang berbeda untuk permintaan awal sampai cukup banyak pekerjaan yang telah dilakukan untuk membenarkan melakukan pekerjaan yang diperlukan untuk mengatur tabel, meskipun Anda bisa berpendapat bahwa Anda perlu menghabiskan$O(n)$ waktu membangun pohon di tempat pertama dan bahwa ini tidak akan mempengaruhi runtime keseluruhan.

Jadi, secara ringkas, idenya adalah sebagai berikut:

• Alih-alih menggunakan pohon biner yang ditambah, gunakan yang ditambah $k$pohon -ary.
• Perhatikan itu dengan kecil $k$, semuanya mungkin $k$daftar-bit dan permintaan pada daftar tersebut dapat dihitung sebelumnya.
• Gunakan struktur data yang dikomputasi ini di setiap node di pohon.
• Memilih $k = \frac{\lg n}{2}$ untuk membuat pohon tinggi, dan, karenanya, biaya per operasi, $O(\frac{\log n}{\log \log n})$.
• Hindari biaya precomputation dimuka dengan menggunakan struktur data penggantian sementara di setiap node sampai precomputation menjadi berharga.

Secara keseluruhan, ini adalah struktur data yang pintar. Terima kasih telah mengajukan pertanyaan ini dan menautkannya - saya belajar banyak dalam prosesnya!

Sebagai tambahan, banyak teknik yang masuk ke struktur data ini adalah strategi umum untuk mempercepat solusi yang tampaknya optimal. Gagasan untuk mengkomputasi semua kueri yang mungkin pada objek berukuran kecil sering disebut Metode Empat Rusia dan dapat dilihat dalam struktur data lain seperti struktur data Fischer-Heun untuk rentang kueri minimum atau algoritma decremental untuk konektivitas pohon. Demikian pula, teknik menggunakan pohon multi-jalan seimbang yang ditambah dengan faktor percabangan logaritmik muncul dalam konteks lain, seperti struktur data deterministik asli untuk konektivitas grafik dinamis, di mana pendekatan seperti itu digunakan untuk mempercepat permintaan konektivitas dari$O(\log n)$ untuk $O(\frac{\log n}{\log \log n})$.