Décomposition des racines

Nous avons un problème sur la façon de calculer rapidement les sommes sur l'intervalle l...r dans un tableau statique a en moins de O(n) asymptotique.

Divisons le tableau a en k blocs de même taille et calculons d'abord la somme des éléments pour chacun d'eux.

Maintenant, en répondant à la requête, nous pouvons parcourir les éléments du tableau a et les ajouter au résultat, même si l'un des blocs se trouve à l'intérieur du segment, alors nous pouvons ajouter sa somme au résultat et ignorer le éléments de ce bloc.

Le nombre maximum d'opérations par requête avec cet algorithme est n / k + k, donc le k optimal est égal à la racine carrée de n.

 

Nous avons un problème sur la façon de calculer rapidement les sommes sur l'intervalle l...r dans le tableau a, dans lequel les éléments peuvent changer un à la fois, en asymptotique inférieure à O(n).

Cette tâche est résolue de la même manière que la précédente, mais lors d'une demande de modification, vous devez modifier le montant dans le bloc correspondant.

Une tâche est donnée dans laquelle il faut effectuer des opérations en masse sur un segment et reconnaître un élément par index.

Les opérations de masse sont effectuées sous la forme d'un calcul de somme sur un segment.

Pour chaque bloc, nous stockons la modification dans ce bloc, et lors de la demande d'un élément de ce bloc, nous prenons cette information en compte.