Penguraian akar

Kami menghadapi masalah tentang cara mengira dengan cepat jumlah pada selang l...r dalam tatasusunan statik a dalam kurang daripada O(n) asimptotik.

Mari kita bahagikan tatasusunan a kepada blok k yang sama saiz dan mula-mula hitung jumlah elemen bagi setiap satu daripadanya.

Sekarang, apabila menjawab permintaan, kita boleh melalui elemen tatasusunan a dan menambahkannya pada hasil, juga jika salah satu blok terletak di dalam segmen, maka kita boleh menambah jumlahnya pada hasil dan melangkau elemen blok ini.

Bilangan maksimum operasi bagi setiap pertanyaan dengan algoritma ini ialah n / k + k, jadi k optimum adalah sama dengan punca kuasa dua n.

 

Kami menghadapi masalah tentang cara mengira dengan cepat jumlah pada segmen l...r dalam tatasusunan a, di mana unsur boleh berubah satu demi satu, dalam asimptotik kurang daripada O(n).

Tugas ini diselesaikan sama seperti yang sebelumnya, tetapi apabila meminta perubahan, anda perlu menukar jumlah dalam blok yang sepadan.

Tugas diberikan di mana ianya perlu untuk menjalankan operasi pukal pada segmen dan mengenali elemen mengikut indeks.

Operasi besar-besaran dijalankan sebagai pengiraan jumlah pada segmen.

Untuk setiap blok, kami menyimpan perubahan dalam blok itu dan apabila meminta elemen daripada blok itu, kami mengambil kira maklumat tersebut.