¿Cuál es la diferencia entre Segment Tree y Fenwick Tree en términos de operaciones?

Al igual que con cualquier estructura de datos que realice operaciones en subsegmentos, necesita asociatividad.

Fenwick Tree (o BIT – Binary Indexed Tree) es menos poderoso que Segment Tree: solo puede calcular sumas de prefijo , mientras que Segment Tree puede calcular sumas en cualquier subsegmento.

Siempre que solo necesite sumas de prefijos, puede realizar cualquier operación asociativa. En el momento en que desea utilizar BIT para operaciones en subsegmentos, debe aplicar algunos trucos sobre BIT.

• Cómo resolver el problema de cambio de UVa 166 si tenemos una oferta limitada de cada denominación
• ¿Cómo funciona el algoritmo de acortador de URL?
• ¿Cuál es la forma más eficiente de ordenar un millón de enteros de 32 bits?
• ¿Por qué deberíamos conocer más de un algoritmo de clasificación en Python (burbuja, inserción, selección) si todos están haciendo el mismo trabajo?
• Cómo verificar si un número es un primo retorcido o no usa bucle

El truco más popular es “restar” dos sumas de prefijos. Para hacer eso, la asociatividad no es suficiente: también necesita un elemento inverso y, en consecuencia, un elemento de identidad. Entonces. Su operación debe formar un grupo , no un semigrupo.

Algunos ejemplos de solicitudes que se pueden calcular utilizando el árbol de segmentos, pero no BIT:

1. Intuitivamente: cualquier operación que pierde mucha información sobre la estructura interna de un segmento. Por ejemplo, máximo.
2. O el que escribí en mi otra respuesta: conteo de elementos máximos.
3. O desde allí, el subsegmento más largo de un subsegmento que solo contiene ceros.
4. Multiplicación. Es imposible dividir por cero. O bien, si la multiplicación se realiza en un módulo, a veces el resultado de la división no se define de forma exclusiva (por ejemplo, 2 * 8 = 8 * 8 = 0 mod 16). Estrictamente hablando, es posible usar algunos trucos (por ejemplo, contar ceros o divisores no primos por separado), pero es mucho más difícil y no vale la pena.
5. Multiplicación matricial. Nuevamente, la matriz inversa no es única (y a veces inexistente), pero no conozco ningún truco que permita convertir la multiplicación de la matriz en un grupo.