Pour trouver la somme de tous les sous-ensemble consécutif de longueur k dans un tableau donné

Question

Je veux tout savoir la somme des sous-réseau continu de longueur K pour un tableau donné de longueur n étant donné que k < n. Par exemple, laissez le tableau donné être arr[6]={1,2,3,4,5,6} et k=3, puis la réponse est (6,9,12,15). Il peut être obtenu que:

(1+2+3)=6, 
(2+3+4)=9, 
(3+4+5)=12, 
(4+5+6)=15. 

Je l'ai essayé en utilisant la fenêtre coulissante de longueur k, mais sa complexité de temps est O(n) .est une solution qui prend encore moins de temps tels que O(log n).

Answer 1

Si vous ne connaissez pas certaines propriétés spécifiques du tableau (par exemple, l'ordre des éléments, la plage des éléments inclus dans le tableau, etc.), vous devez vérifier chaque valeur, ce qui entraîne une complexité O(n).

Si, par exemple, vous saviez que la somme des valeurs du tableau étaient T (peut-être parce que vous saviez T lui-même ou a été donné la plage), vous pouvez alors considérer que tous les éléments sauf le premier et le dernier (K-1) éléments seraient inclus dans K sommes différentes. Cela signifierait une somme de T.K moins une certaine quantité, et vous pourriez réduire les valeurs de la première et la dernière K valeurs appropriées quantité de fois, ce qui entraîne un algorithme de complexité O(K).

Mais notez que, pour réaliser une stratégie similaire à celle-ci, vous devriez connaître d'autres informations spécifiques concernant les valeurs dans le tableau, que ce soit leur portée ou leur somme.

Answer 2

Vous pouvez utiliser la structure de données Arborescence de segments, bien que sa construction prenne O (n log n), mais que vous puissiez trouver la somme de tout intervalle dans O (log n) et modifier chaque élément de tableau dans O log n) https://en.wikipedia.org/wiki/Segment_tree