c++ - programacion - int16 valor maximo
¿Qué significa(número y número) en la programación de bits? (3)
Esta pregunta ya tiene una respuesta aquí:
- significado de (número) y (-número) 3 respuestas
Por ejemplo:
int get(int i) {
int res = 0;
while (i) {
res = (res + tree[i]) % MOD;
i -= ( (i) & (-i) );
}
return res;
}
Una función de actualización de árbol:
void update(int i, int val) {
while (i <= m) {
tree[i] = (tree[i] + val) % MOD;
i += ( (i) & (-i) );
}
}
¿Puede explicar qué hacen en el código utilizando
( (i) & (-i) )
?
En caso de que alguien quisiera una prueba más general también,
Suponga que
x
tiene el formato a10
k
(es decir, algunas cadenas de bits a, seguidas de un 1, seguidas de k ceros).
-x
es (por definición) lo mismo que
~x + 1
, entonces
- x & -x = (completar)
- a10 k & - (a10 k ) = (def. de negación)
- a10 k & ~ (a10 k ) + 1 = (aplicar inversión)
- a10 k & ~ a01 k + 1 = (sumar 1)
- a10 k & ~ a10 k = (Y entre algo y su inverso)
- 0 w 10 k
Por lo tanto, nos queda solo ese 1 más a la derecha que supusimos que existía.
La suposición sobre la forma de
x
deja fuera el caso de que
x = 0
, en cuyo caso el resultado es obviamente cero.
Estas dos funciones son una implementación modificada de una estructura de datos del
árbol de índice binario (árbol de Fenwick)
.
Aquí hay dos imágenes para complementar la respuesta de MikeCAT que muestra cómo modifico las actualizaciones para diferentes valores.
La función "get":
Supongamos que el valor máximo de la entrada en la función es 15 para simplificar la representación.
Un nodo con el número
t
en él representa el
árbol [t]
en la matriz de árbol.
Si llama
a la
función
get
para
i,
el valor devuelto es la suma del
árbol [i]
más la suma de todos
los
elementos de la matriz de
árbol
que su índice en la matriz es padre de
i
en la imagen, excepto cero.
Aquí hay unos ejemplos:
get(15) = tree[15] + tree[14] + tree[12] + tree[8]
get(14) = tree[14] + tree[12] + tree[8]
get(13) = tree[13] + tree[12] + tree[8]
get(12) = tree[12] + tree[8]
get(11) = tree[11] + tree[10] + tree[8]
get(10) = tree[10] + tree[8]
get(9) = tree[9] + tree[8]
get(8) = tree[8]
get(7) = tree[7] + tree[6] + tree[4]
get(6) = tree[6] + tree[4]
get(5) = tree[5] + tree[4]
get(4) = tree[4]
get(3) = tree[3] + tree[2]
get(2) = tree[2]
Los números en las etiquetas de los nodos en la imagen de arriba tienen la propiedad de que el padre de cada nodo es esa etiqueta de nodo menos la menos significativa 1 (explicado muy bien en la respuesta de @MikeCAT)
La función "actualizar":
Para simplificar la imagen, supongamos que la longitud máxima de la matriz de
árbol
es 16.
La función de
actualización
es un poco más complicada.
Agrega
val
al
árbol [i]
y a todos
los
elementos del
árbol
que su índice es padre del nodo con la etiqueta
i
en la imagen.
update(16, val) --> tree[16] += val;
update(15, val) --> tree[15] += val, tree[16] += val;
update(14, val) --> tree[14] += val, tree[16] += val;
update(13, val) --> tree[13] += val, tree[14] += val; tree[16] += val;
update(12, val) --> tree[12] += val, tree[16] += val;
update(11, val) --> tree[11] += val, tree[12] += val, tree[16] += val;
update(10, val) --> tree[10] += val, tree[12] += val, tree[16] += val;
update(9, val) --> tree[9] += val, tree[10] += val, tree[12] += val, tree[16] += val;
update(8, val) --> tree[8] += val, tree[16] += val;
update(7, val) --> tree[7] += val, tree[8] += val, tree[16] += val;
update(6, val) --> tree[6] += val, tree[8] += val, tree[16] += val;
update(5, val) --> tree[5] += val, tree[6] += val, tree[8] += val, tree[16] += val;
update(4, val) --> tree[4] += val, tree[8] += val, tree[16] += val;
update(3, val) --> tree[3] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(2, val) --> tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
update(1, val) --> tree[1] += val, tree[2] += val, tree[4] += val, tree[8] += val, tree[16] += val;
Permítanme suponer que el valor negativo se representa usando el complemento a dos.
En este caso,
-i
se puede calcular como
(~i)+1
(voltear bits, luego agregar 1).
Por ejemplo, déjame considerar
i = 44
.
Entonces, en binario,
i = 0000 0000 0000 0000 0000 0000 0010 1100
~i = 1111 1111 1111 1111 1111 1111 1101 0011
-i = (~i)+1 = 1111 1111 1111 1111 1111 1111 1101 0100
(i) & (-i) = 0000 0000 0000 0000 0000 0000 0000 0100
Como puede ver, el bit mínimo que es 1 se puede calcular usando
(i) & (-i)
.