Kök ayrışması

O(n)'den küçük asimptotiklerde a statik dizisindeki l...r aralığındaki toplamları hızlı bir şekilde hesaplama konusunda bir sorunumuz var.

a dizisini aynı büyüklükteki k bloğa bölelim ve önce her birinin eleman toplamını hesaplayalım.

Artık talebe cevap verirken a dizisinin elemanlarını gözden geçirip sonuca ekleyebiliriz, ayrıca bloklardan biri segmentin içindeyse onun toplamını sonuca toplayıp sonucu atlayabiliriz. bu bloğun öğeleri.

Bu algoritma ile sorgu başına maksimum işlem sayısı n / k + k'dir, yani optimal k, n'nin kareköküne eşittir.

 

O(n)'den küçük asimptotiklerde elemanların teker teker değişebildiği a dizisindeki l...r segmentindeki toplamların hızlı bir şekilde nasıl hesaplanacağı konusunda bir sorunumuz var.

Bu görev bir öncekine benzer şekilde çözülür, ancak değişiklik talep ederken ilgili bloktaki miktarı değiştirmeniz gerekir.

Bir segment üzerinde toplu işlemler gerçekleştirmenin ve bir öğeyi dizine göre tanımanın gerekli olduğu bir görev verilir.

Toplu işlemler, bir segment üzerinde toplam hesaplaması olarak gerçekleştirilir.

Her blok için değişikliği o blokta saklarız ve o bloktan bir öğe isterken bu bilgiyi dikkate alırız.