Como saben, la división y la fusión se pueden hacer en tiempo logarítmico en promedio. Si desea consultar (digamos, la suma) entre algún rango [L, R]. Luego divida el árbol en tres partes, [1, L-1], [L, R] y [R + 1, N]. Asegúrese de mantener invariantes de nodo mientras lo hace. (Impleméntelo como parte de los procedimientos de división y fusión). Luego solo lea la información requerida del intervalo de consulta. Luego use la operación de fusión para restaurar el árbol original. Suponiendo que el nodo invariante como suma y tamaño del subárbol se pueda calcular en tiempo constante. La complejidad general de la consulta es logarítmica.
Supongo que sabes “treap implícito” donde la clave no está explícitamente. Puede pensarlo como una versión dinámica de una matriz con una sobrecarga logarítmica. De esa manera, puede usarlo como árbol de segmentos dinámicos. Si calcular invariantes es un poco costoso, puede usar la información del tamaño del subárbol para navegar por el árbol y evitar dividir y fusionar los pasos.
Feliz codificación 🙂
- ¿Qué es una matriz?
- ¿Cuáles son las formas de ajustar algoritmos de aprendizaje automático?
- Algoritmos: ¿Cómo reduzco la latencia en HFT?
- Al modelar un autómata determinista de estado finito, ¿qué algoritmo de recorrido gráfico debe usarse?
- Soy un desarrollador web que trabaja en el marco Python Django durante el año pasado. ¿Puedo aprender estructuras de datos y algoritmos si paso solo 2-3 horas diarias?
