sexta-feira, 10 de fevereiro de 2012

Binary Indexed Tree

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: