Imagine que você tem o seguinte problema: você tem N caixas e distribui M bolas nessas caixas e precisa responder duas perguntas:
· O somatório das bolas nas caixas a partir de l até k
· Adicionar novas bolas na caixa i
#define MAXVALUE 20
int f[MAXVALUE+1]; //f[i] = número de bolas na caixa i
int c[MAXVALUE+1]; //c[i] = f[0] + f[1]+ ... + f[i]
/*Complexidade O(1)*/
int range(int a,int b){
return c[b] - c[a-1];
}
/*Complexidade O(MAXVALUE)*/
int insere(int x, int val){
int i;
f[x] += val;
for(i=x;i<MAXVALUE;i++)
c[i] += val;
}
int main(){
int x,i,a,b;
int N=100;
srand(time(NULL));
for(i=0;i<N;i++){
x = rand() % MAXVALUE + 1;
f[x]++;
}
c[1] = f[1];
for(i=2;i<MAXVALUE;i++){
c[i] = f[i] + c[i-1];
}
return 0;
}
i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
f
|
6
|
6
|
5
|
3
|
10
|
12
|
3
|
7
|
5
|
7
|
4
|
6
|
4
|
3
|
3
|
4
|
5
|
7
|
c
|
6
|
12
|
17
|
20
|
30
|
42
|
45
|
52
|
57
|
64
|
68
|
74
|
78
|
81
|
84
|
88
|
93
|
100
|
Note que a inserção val bolas na caixa x modifica todos c[j] para x≤j≤MAXVALUE. Podemos dizer que vários c[j] ficam responsáveis por armezenar a mudança de uma única chave.
Podemos melhorar este algoritmo distribuindo a responsabilidade de uma única chave.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
| |
tree
|
1
|
1..2
|
3
|
1..4
|
5
|
5..6
|
7
|
1..8
|
9
|
9..10
|
11
|
9..12
|
13
|
13..14
|
15
|
1..16
|
17
|
17..18
|
Tabela de responsibilidade
Se alterarmos quisermos adicionar v bolas na caixa 9 vai modificar apenas tree[9] , tree[10] ,tree[12]. Como descobrir quem são os afetados pela alteração da caixa i?
9 = (1001)2
10 = (1010)2
12 = (1100)2
Note que os valores afetados pela alteração da caixa 9 são os valores do vetor tree cujos índices tem a posição do último dígito 1 do número i movidos para a esquerda.
Se quisermos saber quantas bolas temos caixas de 1 até 9, precisamos somar tree[9] + tree[8]. Como descobrir quem são os responsáveis pelo somatório da caixa 1 até a caixa i?
9 = (1001)2
8 = (1000)2
Note que os valores responsáveis pelo somatório da caixa 1 até i são os valores do vetor tree cujos índices tem a posição do último dígito 1 do número i movidos para a direita.
Para descobrir os valores que tem a posição do último dígito 1 do número idx movidos para a esquerda. Basta fazer o seguinte:
idx += (idx & -idx)
O valor de idx pode ser escrito da notação binária como a10b. O valor de –idx tem a seguinte representação:
Para descobrir os valores que tem a posição do último dígito 1 do número idx movidos para a direita. Basta fazer o seguinte:
idx -= (idx & -idx)
O valor de idx pode ser escrito da notação binária como a10b. O valor de –idx tem a seguinte representação:
idx = idx - (idx & -idx)
idx = a10b - 10b
idx = (a-1)0(b+1)
int f[MAXVALUE+1];
int tree[MAXVALUE+1];
int read(int idx){
int sum = 0;
while (idx > 0){
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
void insere(int idx ,int val){
while (idx <= MAXVALUE){
tree[idx] += val;
idx += (idx & -idx);
}
}
int range(int a,int b){
return read(b) - read(a-1);
}
int main(){
int x,i,a,b;
int N=100;
srand(time(NULL));
memset(f,0,sizeof(f));
memset(tree,0,sizeof(tree));
for(i=0;i<N;i++){
x = rand() % MAXVALUE + 1;
f[x]++;
}
for(i=1;i<=MAXVALUE;i++){
update(i,f[i]);
}
return 0;
}
I
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
F
|
6
|
6
|
5
|
3
|
10
|
12
|
3
|
7
|
5
|
7
|
4
|
6
|
4
|
3
|
3
|
4
|
5
|
7
|
C
|
6
|
12
|
17
|
20
|
30
|
42
|
45
|
52
|
57
|
64
|
68
|
74
|
78
|
81
|
84
|
88
|
93
|
100
|
tree
|
6
|
12
|
5
|
20
|
10
|
22
|
3
|
52
|
5
|
12
|
4
|
22
|
4
|
7
|
3
|
88
|
5
|
12
|
1
|
1..2
|
3
|
1..4
|
5
|
5..6
|
7
|
1..8
|
9
|
9..10
|
11
|
11..12
|
13
|
13..14
|
15
|
1..16
|
17
|
17..18
|
Referência:
Nenhum comentário:
Postar um comentário