es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Consultas de multiplicación en un árbol

20 Jul, 2023 Programación

Nos dan un árbol de N nodos (1-N) con cada nodo teniendo un valor inicial A[i]. El árbol tiene como raíz el nodo 1.

Nos dan las consultas Q de tipo:

1 V X: multiplicar todos los nodos en el subárbol de X con el valor V.
2 X: encontrar el valor del nodo X.

Restricciones:

N ≤ 10^5
Q ≤ 10^5

Mi enfoque es el siguiente:

Digamos que tenemos el siguiente árbol como entrada:

   1
 /  \
2    3

/ \ \
4 5 7
/
6

La idea es recorrer el árbol utilizando DFS y construir una matriz de recorrido del árbol que contenga dos valores para cada nodo.

índice: 0 1 2 3 4 5 6
nodo: 1 2 4 6 5 3 7
tamaño del subárbol: 7 4 2 1 1 2 1

y luego creamos un árbol de segmentos utilizando la matriz anterior.

     (0-6)
 /           \

(0-3) (4-6)
/ \ / \
(0-1) (2-3) (4-5) (6)
/ \ / \ / \
(0) (1) (2) (3) (4) (5)

—> Entonces, ahora cuando obtenemos una consulta de tipo 1, digamos, 1 3 2.
necesitamos multiplicar todos los nodos en el subárbol de 2, lo que significa que necesitamos hacer una consulta de actualización en (1-4) en nuestro árbol de segmentos.
En cada nodo de un árbol de segmentos, mantenemos un factor de multiplicación inicial como 1 y lo actualizamos multiplicándolo por el valor ‘V (en este caso = 3)’ cada vez que obtenemos una consulta de tipo 1.
—> Cuando obtenemos una consulta de tipo 2, digamos, 2 4: ahora podemos consultar nuestro árbol de segmentos en (2, 2) y consolidar todos los factores de multiplicación en el camino y multiplicarlos por el valor existente del nodo ‘4’ para devolver el resultado de la consulta.

Con este enfoque, cada consulta se puede resolver en un tiempo de O(log(n)). No pude codificar este enfoque a tiempo.

¿Hay algún otro enfoque más simple para resolver este problema (tal vez sin usar un árbol de segmentos) y según las restricciones, el tiempo de consulta debería ser al menos tan eficiente como O(log(n))?

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Un enfoque posible para resolver este problema sin usar un árbol de segmentos es utilizar una versión modificada de la búsqueda en profundidad (DFS) en el árbol. Podemos realizar un seguimiento de los siguientes valores para cada nodo durante el DFS:

    • el producto de todos los nodos en el subárbol con raíz en el nodo actual (prod)
    • el valor inicial del nodo actual (val)
    • el padre del nodo actual (parent)

    Podemos inicializar estos valores de la siguiente manera:

    • prod = 1 para todos los nodos
    • val = A[i] para cada nodo i
    • parent = -1 para el nodo raíz

    Durante el DFS, podemos actualizar el valor de prod para cada nodo a medida que recorremos el árbol, y usar el valor de prod para responder las consultas de tipo 1. Para responder a las consultas de tipo 2, simplemente podemos devolver el producto de prod y val para el nodo dado.

    Aquí hay un ejemplo de código en Python que implementa este enfoque:

    def dfs(node, parent, A, prod):
    prod[node] = A[node]
    for child in edges[node]:
        if child != parent:
            prod[node] *= dfs(child, node, A, prod)
    return prod[node]

# construir los valores de producto iniciales utilizando DFS
prod = [0] * (n+1)
dfs(1, -1, A, prod)

# procesar las consultas
for q in queries:
    if q[0] == 1:
        v, x = q[1], q[2]
        prod[x] *= v
    else:
        x = q[1]
        print(prod[x] * A[x])

    La complejidad temporal de este enfoque también es O(log(n)) por consulta, ya que la profundidad del árbol es como máximo log(n), y cada nodo se visita como máximo dos veces durante el DFS. Sin embargo, los factores constantes pueden ser mayores que en el enfoque del árbol de segmentos, por lo que vale la pena comparar ambos enfoques en sus datos de entrada para ver cuál es más rápido.

Comments are closed.