Soma de prefixo em C ++

As somas de prefixo são os totais em execução do número de uma matriz. É outra sequência completa de números. Por exemplo, considere a seguinte lista: 5, 2, -6, 8, -4, 0, 9, 3, -1, 7

Existem dez elementos. Imagine um 0 que precede esta lista.

Então 0 + 5 = 5, é a primeira soma do prefixo.
0 + 5 + 2 = 7 é a próxima soma do prefixo.
0 + 5 + 2 + -6 = 1 é a soma do prefixo após.
0 + 5 + 2 + -6 + 8 = 9 é a nova soma do prefixo.

Esse total em execução normalmente continua até o último elemento, 7, na lista especificada. A segunda sequência (lista) tem as somas de prefixo de onze elementos. O primeiro elemento na matriz de somas do prefixo (segunda sequência) é o zero assumido (imaginado). As duas tabelas a seguir, onde a segunda linha para cada tabela possui os índices de matriz baseados em zero, ilustram essas duas seqüências:

Tabela dada
	5	2	-6	8	-4	0	9	3	-1	7
	0	1	2	3	4	5	6	7	8	9

Tabela de soma de prefixo
	5	7	1	9	5	5	14	17	16	23
0	1	2	3	4	5	6	7	8	9	10

A primeira tabela é para a matriz dada e a segunda tabela é para a matriz de soma de prefixo. Se o número de elementos na matriz dada for n, o número de elementos na matriz de soma de prefixo é n+1. Este artigo explica as principais características das somas de prefixo. Nesse contexto, "pré-" significa o que foi adicionado antes. Também pode significar prefixar a matriz de prefixo com zero.

Força bruta

Um programador deve saber o significado da força bruta usada na programação. Força bruta significa resolver um problema usando um algoritmo direto, que geralmente não é tão eficiente (para usar menos tempo e memória) como outro algoritmo cuidadosamente ensinado.

Soma prefixo por força bruta

A fim de produzir a matriz de somas prefixos, por força bruta, para a matriz acima, 5 será observada primeiro como a primeira soma do prefixo. Então 5 e 2 serão adicionados para dar a próxima soma do prefixo, 7. Então 5, 2 e -6 serão adicionados para fornecer a soma do prefixo após 1. Em seguida, 5, 2, -6 e 8 serão adicionados para dar a nova soma do prefixo, 9 e assim por diante. Este procedimento pode ser cansativo.

Causado ou não, o código para produzir a matriz de soma prefixo, do zero assumido, pela força bruta é:

int n = 10;
int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
para (int i = 0; iint sum = 0;
int j;
para (j = 0; jsoma = soma + a [j];

P [j] = soma;

O loop externo itera de 0 a menos de menos de n. O loop interno do loop itera de 0 a i, o índice de iteração do loop externo. Com isso, existem 55 operações principais. A complexidade do tempo para isso é O (n.registro₂n).

Soma de prefixo em tempo linear

A complexidade do tempo anterior é de aproximadamente O (n.registro₂n). O algoritmo pode ser melhorado de modo que as somas sejam produzidas em tempo linear para a complexidade do tempo, O (n). Prefixo neste contexto significa adicionar a soma de todos os elementos anteriores ao elemento dado atual. Considere as duas tabelas anteriores, desenhadas como uma tabela, com algumas modificações:

Tabela de soma de prefixo
Dado:	5	2	-6	8	-4	0	9	3	-1	7
	0 + 5 =	5 + 2 =	7 + -6 =	1 + 8 =	9 + -4 =	5 + 0 =	5 + 9 =	14+3 =	17+ -1 =	16+7 =
0	5	7	1	9	5	5	14	17	16	23
0	1	2	3	4	5	6	7	8	9	10

A primeira linha nesta tabela tem os elementos fornecidos em suas posições designadas. Para a segunda e terceira linhas, o zero inicial é assumido. Para a segunda e terceira linhas, cada elemento é igual à soma de todos os elementos anteriores, mais o elemento atual. A última linha tem os índices de matriz de somas prefixos (baseada em zero). Observe que a matriz de somas do prefixo é um elemento mais longo que a matriz fornecida.

Este algoritmo produz a matriz de soma de prefixo no tempo linear da complexidade do tempo O (n). Isto é, existem aproximadamente n operações. E o código de soma do prefixo recomendado em C ++ para a complexidade do tempo O (n) é:

int n = 10;
int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
para (int i = 1; iP [i] = p [i-1] + a [i-1];

Observe que não há loop aninhado desta vez. As declarações dentro dos parênteses do loop for essencial são essenciais. A operação principal do corpo do loop também é importante. Como antes, o loop for itera de 1 a menor que n+1 e não de 0 a menos de n. A declaração do corpo do loop for:

P [i] = p [i-1] + a [i-1];

Isso significa que o valor atual da matriz fornecida é adicionada à soma anterior do prefixo para fornecer a soma atual do prefixo.

Problema comum para somas de prefixo

Observe que o índice correspondente da matriz de somas do prefixo foi adicionado a ele em comparação com o da matriz dada.

Um problema comum para soma de prefixo é encontrar a soma de uma sub-matriz de elementos consecutivos com eficiência. Esta é a soma de uma fatia. A palavra "com eficiência" significa que um algoritmo de força bruta não deve ser usado. Os índices limitantes para a sub-matriz são x e y. Considere a lista especificada:

5, 2, -6, 8, -4, 0, 9, 3, -1, 7

A soma da sub-matriz do elemento 8 ao elemento 9 é:

8 + -4 + 0 + 9 = 13

8 está no índice 3, para x; e 9 está no índice 6 para y. A maneira eficiente de fazer isso é subtrair a soma do prefixo no índice 2, para a matriz dada, da soma do prefixo no índice 6 para a matriz especificada. Para a matriz de prefixo, estes são índices y+1 e índice x. O 1 a ser adicionado é removido para obter o índice de matriz de prefixo, mostrado abaixo, e o código eficiente é:

int n = 10;
int a [] = 5, 2, -6, 8, -4, 0, 9, 3, -1, 7;
int p [n+1];
P [0] = 0;
int x = 3, y = 6;
para (int i = 1; iP [i] = p [i-1] + a [i-1];

int slicesum = p [y+1] - p [x];
cout<A saída é 13, como esperado, mas de um código eficiente.

Conclusão

As somas de prefixo são os totais em execução dos elementos de uma matriz. Duas matrizes estão envolvidas: a matriz dada e o prefixo produzido Array. A matriz de somas do prefixo é mais longa que a matriz fornecida por um elemento. A operação principal para obter os elementos da matriz de prefixos é: o valor atual na matriz de soma de prefixo é a soma anterior de prefixo, além do valor atual da matriz especificada. Para obter a soma de uma fatia da matriz dada, use: int slicesum = p [y+1] - p [x];

Onde x é o índice de limite inferior da fatia na matriz dada e y é o índice de limite superior da fatia na matriz dada.